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√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.

Authors

• Shachar Lovett
• Raghu Meka

Keywords

• Vectors
• Standards
• Entropy
• Gaussian distribution
• Random variables
• Minimization
• Algorithm design and analysis
• Minimum Variance
• Random Walk
• Fundamental Problem
• Original Proof
• Basic Algebra
• Running Time
• Brownian Motion
• Small Step
• Correction Algorithm
• Proof Of Result
• Proof Of The Existence
• Linear Subspace
• discrepancy
• Gaussian
• random walks