An Improved Bound for the Beck-Fiala Conjecture

In 1981, Beck and Fiala [1] 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 $\operatorname{disc}(A):=\min _{x \in\{ \pm 1\}^{n}}\|A x\|_{\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 [1], or $O(\sqrt{k \log n})$, first proved by Banaszczyk [2].We give an algorithmic proof of an improved bound of $O(\sqrt{k \log \log n})$ whenever $k \geq \log ^{5} n$, thus matching the Beck-Fiala conjecture up to $O(\sqrt{\log \log n})$ for almost the full regime of k.