{"ID":23475018,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19714","arxiv_id":"2609.19714","title":"Improved Algorithms for Beck--Fiala with Bounded Sets","abstract":"We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix $A\\in\\{0,1\\}^{m\\times n}$ with at most $d$ ones per column and at most $s$ ones per row. Let $\\log^*$ denote the iterated logarithm and $\\ell_j$ denote the $j$-fold composition of log. Assume $s\\le\\exp(O(\\sqrt d))$. We provide an efficient algorithm that, for arbitrary sparsity $d$, gives $O(\\sqrt d(1+\\log^*n))$ discrepancy. Moreover, if $d\\ge\\ell_j(n)$ for a fixed integer $j\\ge1$, the algorithm gives $O_j(\\sqrt d)$ discrepancy. The proof is a bootstrapping scheme using the Bansal-Jiang algorithm.","short_abstract":"We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix $A\\in\\{0,1\\}^{m\\times n}$ with at most $d$ ones per column and at most $s$ ones per row. Let $\\log^*$ denote the iterated logarithm and $\\ell_j$ denot...","url_abs":"https://arxiv.org/abs/2609.19714","url_pdf":"https://arxiv.org/pdf/2609.19714v1","authors":"[\"Dylan J. Altschuler\"]","published":"2026-09-17T05:11:01Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"math.CO\",\"math.PR\"]","methods":"[]","has_code":false}