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

arXiv: https://arxiv.org/abs/1708.01079 · HTML: https://mlsanity.com/paper/1708.01079/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2017.

## Built on by (most cited first, 10 of 10)

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Sample Constrained Treatment Effect Estimation](https://mlsanity.com/paper/2210.06594/) (2022)
- [Low-Rank Thinning](https://mlsanity.com/paper/2502.12063/) (2025)
- [Synthetic Principal Component Design: Fast Covariate Balancing with Synthetic Controls](https://mlsanity.com/paper/2211.15241/) (2022)
- [Stronger Coreset Bounds for Kernel Density Estimators via Chaining](https://mlsanity.com/paper/2310.08548/) (2023)
- [Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical](https://mlsanity.com/paper/2209.01147/) (2022)
- [Self-Balancing Sequential Sampling: Fast Convergence with Controlled Predictability](https://mlsanity.com/paper/2607.20818/) (2026)
- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)
- [Product-Aware Deterministic Rounding for Quantized Matrix Multiplication](https://mlsanity.com/paper/2609.31641/) (2026)

## Abstract (arXiv)

An important result in discrepancy due to Banaszczyk states that for any set of n vectors in ℝm of ℓ2 norm at most 1 and any convex body K in ℝm of Gaussian measure at least half, there exists a ± 1 combination of these vectors which lies in 5K. This result implies the best known bounds for several problems in discrepancy. Banaszczyk's proof of this result is non-constructive and a major open problem has been to give an efficient algorithm to find such a ± 1 combination of the vectors. In this paper, we resolve this question and give an efficient randomized algorithm to find a ± 1 combination of the vectors which lies in cK for c>0 an absolute constant. This leads to new efficient algorithms for several problems in discrepancy theory.