Id: arxiv/2607.14238 Url: https://arxiv.org/abs/2607.14238 Tags: math.CO, cs.DM, cs.DS, math.PR Score: 0 Title: Online Beck--Fiala Down to Logarithmic Sparsity Domain: math.CO Source: arxiv Authors: Dylan J. Altschuler, Konstantin Tikhomirov Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-15 Page: https://delphi.science/r/arxiv/2607.14238 The Beck--Fiala conjecture asserts that every matrix $A\in\{0,1\}^{n\times T}$ with at most $d$ nonzero entries in each column has discrepancy $O(\sqrt d)$. A major breakthrough result of Bansal and Jiang recently established the validity of the conjecture for $d \ge \log(T)^2$. The present article extends the validity of the classical \textit{offline} Beck--Fiala conjecture to $d \ge \log(T)^{1+o(1)}$; moreover, the main thrust of the result is that it is actually obtained by an efficient \textit{online} algorithm that minimizes prefix discrepancy. The result is also essentially optimal,…