Theory of Computing
-------------------
Title     : The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues
Authors   : Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett
Volume    : 15
Number    : 21
Pages     : 1-27
URL       : https://theoryofcomputing.org/articles/v015a021

Abstract
--------

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.