Online Beck--Fiala Down to Logarithmic Sparsity

arXiv:2607.14238 · math.CO, cs.DM, cs.DS, math.PR · Submitted 2026-07-15 · Read on arXiv

math.CO, cs.DM, cs.DS, math.PR

Submitted: 2026-07-15

Updated: 2026-11-03

Comments: Minor revision - simplified proof and significantly expanded the exposition

License: http://creativecommons.org/licenses/by/4.0/

The gist: The celebrated (offline) Beck--Fiala conjecture asserts that every matrix A in0,1 n times T with at most d nonzero entries in each column has discrepancy O(sqrt d).

Terminology

Abstract

The celebrated (offline) Beck--Fiala conjecture asserts that every matrix A in0,1 n times T with at most d nonzero entries in each column has discrepancy O(sqrt d). In this note, we consider the online version of the conjecture. For every fixed η>0, we give a randomized online algorithm that achieves O η(sqrt d) prefix discrepancy for every fixed sequence of d-sparse vectors a t in[-1,1] n, except with probability at most [ C ηT [-c ηd over 2+η(ed)].] In particular, this gives an optimal O(sqrt d) discrepancy upper bound for d at least C η(T)(T) 2+η. This range of sparsity is optimal up to T factors. The result also resolves in strong form the online Spencer problem, corresponding to the case d = n. The algorithm is based on a compactly supported Metropolis walk, constructed by combining ideas from several recent works on online vector balancing. The proof was generated in conversation with ChatGPT 5.6 Pro; the authors provided high-level guidance in several rounds of prompting, followed by manual checking and rewriting of the proof.

Sources

Related papers