An Improved Bound for the Beck-Fiala Conjecture

Nikhil Bansal, Haotian Jiang

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} \|Ax\|_\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 \geq \log^5 n$, thus matching the Beck-Fiala conjecture up to $O(\sqrt{\log \log n})$ for almost the full regime of $k$.
BibTeX
@misc{bansal2025improved,
  author = {Nikhil Bansal and Haotian Jiang},
  title = {{An Improved Bound for the Beck-Fiala Conjecture}},
  year = {2025},
  eprint = {2508.01937},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.01937},
}

Loading related content...

Figure