Constructive Discrepancy Minimization for Convex Sets

A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(√n). Recent exciting work of Bansal, Lovett and Meka shows that such colorings can be found in polynomial time. In fact, the Lovett-Meka algorithm finds a half integral point in any "large enough" polytope. However, their algorithm crucially relies on the facet structure and does not apply to general convex sets. We show that for any symmetric convex set K with measure at least e -- n/500, the following algorithm finds a point y ∈ K ∩ [ -- 1, 1]n with Ω(n) coordinates in ±1: (1) take a random Gaussian vector x, (2) compute the point y in K ∩ [ -- 1, 1]n that is closest to x. (3) return y. This provides another truly constructive proof of Spencer's theorem and the first constructive proof of a Theorem of Giannopoulos.

Authors

• Thomas Rothvoss

Keywords

• Vectors
• Polynomials
• Strips
• Convex functions
• Geometry
• Linear programming
• Silicon
• Convex Set
• Proof Of Theorem
• Gaussian Measurement
• Symmetric Set
• Unit Vector
• Random Walk
• Convex Optimization Problem
• Tight Constraints
• Linear Programming Approach
• Discrepancy theory
• combinatorics
• convex optimization