A classic result of Banaszczyk (Random Str. & Algor. 1997) states that given any n vectors in Rm with ℓ2-norm at most 1 and any convex body K in Rm 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.
Additional Metadata
Keywords Discrepancy, Random walks
Persistent URL dx.doi.org/10.4086/toc.2019.v015a021
Journal Theory of Computing
Citation
Bansal, N, Dadush, D.N, Garg, S, & Lovett, S. (2019). The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. Theory of Computing, 15. doi:10.4086/toc.2019.v015a021