An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound

DOI10.1137/17M1126795zbMath1421.68182arXiv1605.02882WikidataQ123151783 ScholiaQ123151783MaRDI QIDQ4634029

Daniel Dadush, Nikhil Bansal, Shashwat Garg

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingdiscrepancyrandom walk

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Randomized algorithms (68W20) Irregularities of distribution, discrepancy (11K38)

Related Items (7)

Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries ⋮ The Phase Transition of Discrepancy in Random Hypergraphs ⋮ The discrepancy of random rectangular matrices ⋮ The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant ⋮ TIGHTER BOUNDS FOR THE DISCREPANCY OF BOXES AND POLYTOPES ⋮ Unnamed Item ⋮ Gaussian discrepancy: a probabilistic relaxation of vector balancing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Discrepancy of set-systems and matrices
• ``Integer-making theorems
• On tail probabilities for martingales
• Deterministic discrepancy minimization via the multiplicative weight update method
• A panorama of discrepancy theory
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Discrepancy Without Partial Colorings
• Approximation Algorithms and Semidefinite Programming
• Approximation-Friendly Discrepancy Rounding
• Six Standard Deviations Suffice
• Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
• On the Beck-Fiala Conjecture for Random Set Systems
• Efficient algorithms for discrepancy minimization in convex sets
• Algorithmic discrepancy beyond partial coloring
• Approximating Hereditary Discrepancy via Small Width Ellipsoids
• An Improvement of the Beck–Fiala Theorem
• Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach

This page was built for publication: An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound