A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(n^1 2). 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 exp(-n 500), the following algorithm finds a point y in K [-1,1]^n with Omega(n) coordinates in -1,+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 Gluskin and Giannopoulos.
@cite_11: Let ‖·‖ be the Euclidean norm on Rn and γn the (standard) Gaussian measure on Rn with density (2π)−n 2e. It is proved that there is a numerical constant c>0 with the following property: if K is an arbitrary convex body in Rn with γn(K)≥1 2, then to each sequence u1,…,um∈Rn with ‖u1‖,…,‖um‖≤c there correspond signs e1,…,em=±1 such that ∑mi=1eiui∈K. This improves the well-known result obtained by Spencer [Trans. Amer. Math. Soc.289, 679–705 (1985)] for the n-dimensional cube. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 351–360, 1998
More generally, the theorem of Banaszczyk @cite_11 shows that for any convex set @math with Gaussian measure at least @math and any set of vectors @math of length @math , there exist signs @math so that @math .