*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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 (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 Raghu Meka
