### Rutgers Discrete Mathematics Seminar

Title: Constructive discrepancy minimization by walking on the edges

Speaker: **Raghu Meka**, IAS

Date: Tuesday, December 4, 2012 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:
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.

See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math