Efficient algorithms for discrepancy minimization in convex sets. Issue 2 (30th January 2018)

• Record Type: Journal Article
• Authors: Eldan, Ronen; Singh, Mohit
• Is Part Of: Random structures & algorithms. Volume 53:Issue 2(2018)
• Page Start: 289
• Page End: 307
• Publication Date: 2018-01-30
• Subjects: combinatorial discrepancy theory -- rounding algorithms; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20763
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : A result of Spencer states that every collection of n sets over a universe of size n has a coloring of the ground set with { − 1, + 1 } of discrepancy O ( n ) . A geometric generalization of this result was given by Gluskin (see also Giannopoulos) who showed that every symmetric convex body K ⊆ R n with Gaussian measure at least e − ϵ n, for a small ϵ > 0, contains a point y ∈ K where a constant fraction of coordinates of y are in { − 1, 1 } . This is often called a partial coloring result. While the proofs of both these results were inherently non‐algorithmic, recently Bansal (see also Lovett‐Meka) gave a polynomial time algorithm for Spencer's setting and Rothvoß gave a randomized polynomial time algorithm obtaining the same guarantee as the result of Gluskin and Giannopoulos. This paper contains several related results which combine techniques from convex geometry to analyze simple and efficient algorithms for discrepancy minimization. First, we prove another constructive version of the result of Gluskin and Giannopoulos, in which the coloring is attained via the optimization of a linear function. This implies a linear programming based algorithm for combinatorial discrepancy obtaining the same result as Spencer. Our second result suggests a new approach to obtain partial colorings, which is also valid for the non‐symmetric case. It shows that every (possibly non‐symmetric) convex body K ⊆ R n, with Gaussian measure at least e − ϵ n, for a small ϵ > 0, contains a point y ∈ K where a constant fraction of coordinates of y are in { − 1, 1 } . Finally, we give a simple proof that shows that for any δ > 0 there exists a constant c > 0 such that given a body K with γ n ( K ) ≥ δ, a uniformly random x from { − 1, 1 } n is in cK with constant probability. This gives an algorithmic version of a special case of the result of Banaszczyk.