A new SDP-guided Brownian-rounding technique, decoupling via affine spectral-independence, proves discrepancy O(√k) for degree-k set systems with k ≥ log² n and Õ(log^{1/4} n) for unit-norm matrices.
The Komlos Conjecture Holds for Vector Colorings
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The Komlos conjecture in discrepancy theory states that for some constant K and for any m by n matrix A whose columns lie in the unit ball there exists a +/- 1 vector x such that the infinity norm of Ax is bounded above by K. This conjecture also implies the Beck-Fiala conjecture on the discrepancy of bounded degree hypergraphs. Here we prove a natural relaxation of the Komlos conjecture: if the columns of A are assigned unit real vectors rather than +/- 1 then the Komlos conjecture holds with K=1. Our result rules out the possibility of a counterexample to the conjecture based on semidefinite programming. It also opens the way to proving tighter efficient (polynomial-time computable) upper bounds for the conjecture using semidefinite programming techniques.
fields
math.CO 1years
2025 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Decoupling via Affine Spectral-Independence: Beck-Fiala and Koml\'os Bounds Beyond Banaszczyk
A new SDP-guided Brownian-rounding technique, decoupling via affine spectral-independence, proves discrepancy O(√k) for degree-k set systems with k ≥ log² n and Õ(log^{1/4} n) for unit-norm matrices.