Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds beyond Banaszczyk

The Beck-Fiala Conjecture [Beck and Fiala, Discrete Appl. Math., 1981] asserts that any set system of n elements with degree k has combinatorial discrepancy O(√k). A substantial generalization is the Komlós Conjecture, which states that any m × n matrix with columns of unit ℓ2 length has discrepancy O(1). In this work, we resolve the Beck-Fiala Conjecture for k ≥ log2 n. We also give an O(√k + √logn) bound for k ≤ log2 n, where O(·) hides poly(loglogn) factors. These bounds improve upon the O(√k logn) bound in [Banaszczyk, Random Struct. Algor., 1998]. For the Komlós problem, we give an O(log1/4 n) bound, improving upon the previous O(√logn) bound [Banaszczyk, Random Struct. Algor., 1998]. All of our results also admit efficient polynomial-time algorithms To obtain these results, we exploit a new technique of “decoupling via affine spectral-independence” in designing rounding algorithms. In particular, our algorithms obtain the desired colorings via a discrete Brownian motion, guided by a semidefinite program (SDP). Besides standard constraints used in prior works, we add some extra affine spectral-independence constraints, which effectively decouple the evolution of discrepancies across different rows, and allow us to better control how many rows accumulate large discrepancies at any point during the process. This new technique is quite general and may be of independent interest.