Abstract:

Abstract:
Banaszczyk proved (1998) that given a convex body K with gaussian measure p ≥1/2 and given an arbitrary sequence of vectors from the unit ball, one can balance the sum of these vectors so that it lies in 5K. The proof relies on the monotonicity of the gaussian measure of convex bodies under a certain transform (known as Banaszczyk's transform). In this talk, we provide a new, simpler proof of this monotonicity, relying on a reduction to half-planes. We also show that monotonicity holds for arbitrary convex bodies, at the cost of a doubly exponential rescaling near p=0. Our results indicate a negative answer to a strong form of a vector balancing conjecture due to Banaszczyk and Szarek. This is joint work with P. Nayar.