Title: Combinatorial Discrepancy: A Tutorial
Speaker: Raghu Meka, DIMACS & Institute for Advanced Study
Hosted by James Abello, DIMACS
Date: Monday, June 10, 2013 12:30 - 2:00 and 2:30 - 4:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Co-sponsored by the DIMACS Special Focus on Information Sharing and Dynamic Data Analysis. The tutorial will also be videotaped and made available on the DIMACS web site.
Abstract:
Discrepancy theory grew out of the study of irregularities of distribution and number sequences, or in layman's terms, trying to be an egalitarian economist. From its number theoretic origins in the early nineteenth century, discrepancy theory has developed into a rich and beautiful field over the last three decades. Besides being of importance in combinatorics, discrepancy theory has many applications in computational geome-try, communication complexity, algorithm design, image processing and more. In the first session of this two part tutorial, we will cover several classical results in combinatorial discrepancy theory focusing on Beck's partial coloring method. Along the way, we will illustrate the use of linear algebraic and probabilistic methods in combinatorics. In the second session, we will cover some recent results with special emphasis on algorithmic aspects and applications, which in turn shed new light on existential questions.
Speaker:
Raghu Meka is currently a postdoctoral fellow at the Institute for Advanced Study, Princeton and DIMACS, Rutgers. He received his PhD from the University of Texas at Austin in 2011. He is a recipient of the Bert Kay best dissertation award, the Dean's Excellence award and an MCD fellowship at UT Austin. His main interests are in complexity theory, pseudo-randomness, algo-rithm design, learning theory and more generally, in anything to do with probability.
Tutorial Flyer View the Tutorial
video
For questions or more information, please contact Dr. Eugene Fiorini, Associate Director of DIMACS and Program Coordinator (gfiorini@dimacs.rutgers.edu). The Workshop is organized by the DIMACS REU program (http://dimacs.rutgers.edu/REU/)