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

We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((t log n)1/2), matching the best known non-constructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t1/2 log n) bound. Our result also extends to the more general Komlós setting and gives an algorithmic O(log1/2 n) bound.

• Publication year

  2016

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2016-05-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2016.89arXiv 1605.02882
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Algorithmic discrepancy beyond partial coloring

  2016cited by this paper
• Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem

  2016cited by this paper
• Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems

  2016cited by this paper
• Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method

  2016cited by this paper
• Approximation-Friendly Discrepancy Rounding

  2015cited by this paper
• On the Beck‐Fiala conjecture for random set systems

  2015cited by this paper
• A Panorama of Discrepancy Theory

  2014cited by this paper
• Constructive Discrepancy Minimization for Convex Sets

  2014cited by this paper
• Efficient algorithms for discrepancy minimization in convex sets

  2014cited by this paper
• Discrepancy Without Partial Colorings

  2014cited by this paper
• Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach

  2014cited by this paper
• The Komlos Conjecture Holds for Vector Colorings

  2013cited by this paper
• Approximating Hereditary Discrepancy via Small Width Ellipsoids

  2013cited by this paper
• Approximating Bin Packing within O(log OPT * Log Log OPT) Bins

  2013cited by this paper
• An Improvement of the Beck–Fiala Theorem

  2013cited by this paper
• Approximation Algorithms and Semidefinite Programming

  2012cited by this paper
• The geometry of differential privacy: the sparse and approximate cases

  2012cited by this paper
• Constructive Discrepancy Minimization by Walking on the Edges

  2012cited by this paper
• Tight hardness results for minimizing discrepancy

  2011cited by this paper
• The entropy rounding method in approximation algorithms

  2011cited by this paper
• Constructive Algorithms for Discrepancy Minimization

  2010cited by this paper
• Geometric Discrepancy: An Illustrated Guide

  2009cited by this paper
• The Discrepancy Method: Randomness and Complexity

  2000cited by this paper
• Balancing vectors and Gaussian measures of n-dimensional convex bodies

  1998cited by this paper
• Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems

  1997cited by this paper
• Discrepancy of Set-systems and Matrices

  1986cited by this paper
• Six standard deviations suffice

  1985cited by this paper
• "Integer-making" theorems

  1981cited by this paper
• On Tail Probabilities for Martingales

  1975cited by this paper
• Reproduction

  1975cited by this paper

• Near-feasible Fair Allocations in Two-sided Markets

  2025cites this paper
• Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk

  2025cites this paper
• An Improved Bound for the Beck-Fiala Conjecture

  2025cites this paper
• Online Edge Coloring Is (Nearly) as Easy as Offline

  2024influential citation
• On Distributional Discrepancy for Experimental Design with General Assignment Probabilities

  2024influential citation
• Asymptotic Bounds and Online Algorithms for Average-Case Matrix Discrepancy

  2024cites this paper
• Revisit the Partial Coloring Method: Prefix Spencer and Sampling

  2024influential citation
• Colorful vector balancing

  2023cites this paper
• Streaming Semidefinite Programs: O(√n) Passes, Small Space and Fast Runtime

  2023cites this paper
• Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory

  2023cites this paper
• On the Gap between Hereditary Discrepancy and the Determinant Lower Bound

  2023cites this paper
• Sparse Geometric Set Systems and the Beck-Fiala Conjecture

  2023cites this paper
• High Quality Consistent Digital Curved Rays via Vector Field Rounding

  2022cites this paper
• Synthetic Principal Component Design: Fast Covariate Balancing with Synthetic Controls

  2022cites this paper
• Discrepancy Minimization via Regularization

  2022cites this paper
• 1 Part 1 : The Multidimensional Apportionment Problem 1 . 1

  2022influential citation
• Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical

  2022cites this paper
• Fast Discrepancy Minimization with Hereditary Guarantees

  2022cites this paper
• A Unified Approach to Discrepancy Minimization

  2022cites this paper
• Flow time scheduling and prefix Beck-Fiala

  2022cites this paper
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation

  2021cites this paper
• The discrepancy of random rectangular matrices

  2021cites this paper
• Solving Tall Dense SDPs in the Current Matrix Multiplication Time

  2021cites this paper
• A Gaussian fixed point random walk

  2021cites this paper
• Multidimensional Apportionment through Discrepancy Theory

  2021cites this paper
• On Shallow Packings and Tusnády's Problem

  2021cites this paper
• Gaussian discrepancy: a probabilistic relaxation of vector balancing

  2021cites this paper
• Matrix discrepancy from Quantum communication

  2021cites this paper
• The discrepancy of unsatisfiable matrices and a lower bound for the Komlós conjecture constant

  2021cites this paper
• A new framework for matrix discrepancy: partial coloring bounds via mirror descent

  2021cites this paper
• Online Discrepancy with Recourse for Vectors and Graphs

  2021cites this paper
• Asymptotic Geometric Analysis, Part II

  2021cites this paper
• Improved Algorithms for Combinatorial Discrepancy

  2020cites this paper
• A Faster Interior Point Method for Semidefinite Programming

  2020cites this paper
• Online Discrepancy Minimization for Stochastic Arrivals

  2020cites this paper
• New Nearly-Optimal Coreset for Kernel Density Estimation

  2020cites this paper
• Discrepancy minimization via a self-balancing walk

  2020cites this paper
• Generalised Pattern Matching Revisited

  2020cites this paper
• A note on norms of signed sums of vectors

  2019cites this paper
• Online vector balancing and geometric discrepancy

  2019cites this paper
• Four Deviations Suffice for Rank 1 Matrices

  2019cites this paper
• THE UNIVERSITY OF CHICAGO SPHERICAL DISCREPANCY A DISSERTATION SUBMITTED TO THE FACULTY OF THE DIVISION OF THE PHYSICAL SCIENCES IN CANDIDACY FOR THE DEGREE OF MASTER OF SCIENCE DEPARTMENT OF COMPUTER SCIENCE BY CHRIS JONES

  2019cites this paper
• Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization

  2019cites this paper
• D S ] 5 A ug 2 01 9 Algorithms to Approximate Column-Sparse Packing Problems ∗

  2019cites this paper
• Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere

  2019cites this paper
• Balancing Vectors in Any Norm

  2018cites this paper
• Algorithms for combinatorial discrepancy

  2018influential citation
• Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems

  2018cites this paper
• On a generalization of iterated and randomized rounding

  2018influential citation
• On the discrepancy of random low degree set systems

  2018cites this paper
• A Fourier-Analytic Approach for the Discrepancy of Random Set Systems

  2018cites this paper
• Constructive Discrepancy Minimization with Hereditary L2 Guarantees

  2017cites this paper
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

  2017cites this paper
• Tighter Bounds for the Discrepancy of Boxes and Polytopes

  2017cites this paper
• The Gram-Schmidt walk: a cure for the Banaszczyk blues

  2017cites this paper
• Algorithms in Discrepancy Theory and Lattices

  2017influential citation
• Algorithms to Approximate Column-sparse Packing Problems

  2017cites this paper
• Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem

  2016cites this paper
• Tusnády's problem, the transference principle, and non-uniform QMC sampling

  2016cites this paper
• Algorithmic discrepancy beyond partial coloring

  2016cites this paper
• Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method

  2016cites this paper
• Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings

  2015cites this paper
• On the Beck‐Fiala conjecture for random set systems

  2015cites this paper
• Efficient algorithms for discrepancy minimization in convex sets

  2014cites this paper
• Constructive ℓ 2 -Discrepancy Minimization with Additive Deviations

  year unknowncites this paper
• Discrepancy theory and related algorithms

  year unknowninfluential citation