{"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","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-15","reactions":{}}