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

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series - April 8, 2013

Linda Casals lindac at
Thu Apr 4 08:56:55 EDT 2013


DIMACS/CCICADA Interdisciplinary Seminar Series Presents
Title: Constructive Discrepancy Minimization by Walking on the Edges

Speaker: Raghu Meka, DIMACS, Rutgers University and IAS

Date: Monday, April 8, 2013 11:00am - 12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University                 
             Busch Campus, Piscataway, NJ


Minimizing the discrepancy of a set system is a fundamental problem in
combinatorics. One of the cornerstones in this area is the celebrated
six standard deviations result of Spencer (AMS 1985): In any system of
n sets in a universe of size n, there always exists a coloring which
achieves discrepancy 6sqrt{n}. The original proof of Spencer was
existential in nature, and did not give an efficient algorithm to find
such a coloring. Recently, a breakthrough work of Bansal (FOCS 2010)
gave an efficient algorithm which finds such a coloring. In this work
we give a new randomized algorithm to find a coloring as in Spencer's
result based on a restricted random walk we call "Edge-Walk". Our
algorithm and its analysis use only basic linear algebra and is
"truly"constructive in that it does not appeal to the existential
arguments, giving a new proof of Spencer's theorem and the partial
coloring lemma.

Joint work with Shachar Lovett. 

DIMACS/CCICADA Interdisciplinary Series Calendar 2013-

More information about the Dimacs-ccicada-announce mailing list