- Start Date:
June 10, 2013
- Event Start Time:
12:30 PM
- Event End Time:
1:30 PM
- Organizers:
Gene Fiorini
- Seminar Series:
REU Seminar
- Presenter(s):
Raghu Meka - Rutgers University
- Event Location:
DIMACS Seminar room
- 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 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 geometry, 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 and suggest new questions pertaining to existential ones.
Bio: 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, algorithm design, learning theory and more generally in anything to do with probability.
