{"ID":2887444,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.01937","arxiv_id":"2508.01937","title":"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} \\|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$.","short_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})$. Previous...","url_abs":"https://arxiv.org/abs/2508.01937","url_pdf":"https://arxiv.org/pdf/2508.01937v1","authors":"[\"Nikhil Bansal\",\"Haotian Jiang\"]","published":"2025-08-03T22:16:43Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}