Answers are grounded in this paper and cite their sources.
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 [Trans. Amer. Math. Soc., 289 (1985), pp. 679--706]: 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 [Proceedings of FOCS, 2010, pp. 3--10] 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.
No takes yet. Share an insight, caveat, or question.
Lovett et al. (2015) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: