Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] REU Tutorial: Combinatorial Discrepancy

Linda Casals lindac at
Thu Jun 6 11:28:02 EDT 2013

REU Tutorial: Combinatorial Discrepancy
Title: Combinatorial Discrepancy: A Tutorial

Speaker: Raghu Meka, DIMACS & Institute for Advanced Study Hosted by James

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.

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


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.
For questions or more information, please contact Dr. Eugene Fiorini,
Associate Director of DIMACS and Program Coordinator
(gfiorini at The Workshop is organized by the DIMACS REU
program (

Linda Casals
DIMACS Publicity Coordinator
DIMACS Center Rutgers University
96 Frelinghuysen Road
Piscataway, NJ  08854-8018 

More information about the Dimacs-ccicada-announce mailing list