An Improved Bound for the Beck-Fiala Conjecture

Abstract

In 1981, Beck and Fiala [Discrete Appl. Math, 1981] conjectured that given a set system $A\in \{0,1{\}}^{m\times n}$ with degree at most $k$ (i.e., each column of $A$ has at most $k$ non-zeros), its combinatorial discrepancy $\mathsf{disc}(A):={\min }_{x\in \{\pm 1{\}}^n}\Vert Ax{\Vert }_{\infty }$ is at most $O(\sqrt{k})$. Previously, the best-known bounds for this conjecture were either $O(k)$, first established by Beck and Fiala [Discrete Appl. Math, 1981], or $O(\sqrt{k\log n})$, first proved by Banaszczyk [Random Struct. Algor., 1998]. We give an algorithmic proof of an improved bound of $O(\sqrt{k\log \log n})$ whenever $k\ge {\log }^{5}n$, thus matching the Beck-Fiala conjecture up to $O(\sqrt{\log \log n})$ for almost the full regime of $k$.

To appear in FOCS 2025. The result in this paper is subsumed by follow-up work by the authors