An Improved Bound for the Beck-Fiala Conjecture

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{d}\mathsf{i}\mathsf{s}\mathsf{c}(A):={\min }_{x\in \{\pm 1{\}}^n}\mathrm{\parallel }Ax{\mathrm{\parallel }}_{\mathrm{\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$.