***********************************
* Princeton Discrete Math Seminar *
***********************************
Date: Thursday 19th April, 2.15 in Fine Hall 224
Speaker: Raghu Meka, IAS
Title: Constructive discrepancy minimization by walking on the edges
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
6\sqrt{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. His algorithm was based on an SDP relaxation of the discrepancy
problem and a clever rounding procedure. 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.
-----------
Next week: Avi Wigderson
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)