Online Beck--Fiala Down to Logarithmic Sparsity
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
- Optimal Online Discrepancy Minimization in Linear Time
- Decoupling via Affine Spectral-Independence: Beck-Fiala and Koml'os Bounds Beyond Banaszczyk
- On-Line Balancing of Random Inputs
- Optimal Online Discrepancy Minimization
- Discrepancy and Fisher information
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality