Journal
SIAM JOURNAL ON COMPUTING
Volume 46, Issue 1, Pages 224-234Publisher
SIAM PUBLICATIONS
DOI: 10.1137/141000282
Keywords
discrepancy theory; discrete math; convex geometry
Ask authors/readers for more resources
A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(root 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 enoughpolytope. 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 Gaussian measure at least e-n/500, the following algorithm finds a point y epsilon K boolean AND [-1, 1](n) with O(n) coordinates in +/- 1: (1) take a random Gaussian vector x; (2) compute the point y in K boolean AND[-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 Gluskin and Giannopoulos.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available