The Gram-Schmidt walk: a cure for the Banaszczyk blues

DOI10.1145/3188745.3188850zbMath1427.68328arXiv1708.01079OpenAlexW2744926673MaRDI QIDQ5230322

Daniel Dadush, Shachar Lovett, Shashwat Garg, Nikhil Bansal

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.01079

zbMATH Keywords

random walksdiscrepancyrounding techniques

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items (10)

Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ Near-optimal coresets of kernel density estimates ⋮ The discrepancy of random rectangular matrices ⋮ Vector balancing in Lebesgue spaces ⋮ The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Gaussian discrepancy: a probabilistic relaxation of vector balancing ⋮ Unnamed Item

This page was built for publication: The Gram-Schmidt walk: a cure for the Banaszczyk blues