The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues

A classic result of Banaszczyk (Random Str. & Algor. 1997) states that given any n vectors in R^m with ℓ₂-norm at most 1 and any convex body K in R^m of Gaussian measure at least half, there exists a ±1 combination of these vectors that lies in 5K. Banaszczyk’s proof of this result was non-constructive and it was open how to find such a ±1 combination in polynomial time. In this paper, we give an efficient randomized algorithm to find a ±1 combination of the vectors which lies in cK for some fixed constant c > 0. This leads to new efficient algorithms for several problems in discrepancy theory.