Volume 15 (2019) Article 21 pp. 1-27
The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues
Received: July 24, 2018
Revised: December 13, 2019
Published: December 23, 2019
Download article from ToC site:
[PDF (311K)] [PS (1727K)] [Source ZIP]
Keywords: discrepancy, random walks
ACM Classification: F.2.2, G.3
AMS Classification: 68W20

Abstract: [Plain Text Version]

A classic result of Banaszczyk (Random Str. & Algor. 1997) states that given any $n$ vectors in $\mathbb{R}^m$ with $\ell_2$-norm at most $1$ and any convex body $K$ in $\mathbb{R}^m$ of Gaussian measure at least half, there exists a $\pm 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 $\pm 1$ combination in polynomial time. In this paper, we give an efficient randomized algorithm to find a $\pm 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.

-----------------

A conference version of this paper appeared in the Proceedings of the 50th ACM Symposium on Theory of Computing, 2018.