Combinatorics Seminar
When: Sunday, November 4, 10am
Where: Schreiber 309
Speaker: Shachar Lovett, Institute for Advanced Study
Title: Constructive Discrepancy Minimization by Walking
on The Edges
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 (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 Raghu Meka.