Online Spencer discrepancy bounds

For T=n vectors in [−1,1]ⁿ fixed before the algorithm runs, can online signs keep every prefix discrepancy O(√n)? The related targets extend this order to sparse columns and longer horizons under their stated probability assumptions.

Why it matters and what counts as progress

Why it matters: It asks for online balance at Spencer’s scale without seeing future vectors, with separate quantitative extensions for sparsity and horizon.

What counts as progress: An O(√n) online prefix bound for every obliviously fixed sequence of n vectors, or quantitatively stronger sparse and longer-horizon variants.

How the problem developed

1981 · Conjecture [1]
József Beck and Tibor Fiala Established bounded-degree discrepancy bounds and posed the square-root Beck–Fiala discrepancy conjecture that motivates the sparse online variant.
15 Jul 2026 · Upper bound [2]
Dylan J. Altschuler and Konstantin Tikhomirov Reported an O(√n) online prefix-discrepancy bound in Spencer’s setting and extended the method to logarithmic sparsity in the online Beck–Fiala setting.

AI contribution

Online Beck--Fiala Down to Logarithmic Sparsity

Dylan J. Altschuler, Konstantin Tikhomirov

For every fixed sequence of T=n vectors in [−1,1]^n chosen before the algorithm runs, the model-generated proof gives O(√n) maximum online prefix discrepancy. The authors also prove longer-horizon and sparse-column extensions, including O(√n) for T up to exp(cn/log^(2+η)(en)) with the stated high probability.

AI involvementAI-centered

ImportanceMajor

Technical verificationFormal (human)

Human understandingFull