The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Published Web Location
https://dl.acm.org/doi/pdf/10.1145/3188745.3188850Abstract
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.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.