Papers › The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
An important result in discrepancy due to Banaszczyk states that for any set of n vectors in ℝᵐ of ℓ₂ norm at most $1$ and any convex body K in ℝᵐ 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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections