What was already known
Earlier online Komlós bounds were O(√log T), while the online Spencer question was open. The authors combined prior coupling and bounded-walk ingredients in a new compact Metropolis walk.
AI involvement
Altschuler and Tikhomirov chose the high-level strategy. ChatGPT 5.6 Pro supplied the initial complete proof and bump density; the authors manually checked, rewrote and extended it.
The human authors chose the key ingredients and problem; the model supplied the complete initial proof and new bump density central to the retained result.
Importance
Resolves the online Spencer question and improves online sparse Beck–Fiala discrepancy bounds.
Limitations
The sequence is obliviously fixed in advance; the result does not cover an adaptive adversary. The longer-horizon statement uses its stated probability and parameter conditions.
Technical verification
The named authors explicitly report manual verification of the proofs in the paper, including the assessed original Spencer result. This is source-reported complete human checking, not independently reproduced here.
Formal checking
Manual verification and rewriting of model-generated proofs
- Checker
- Dylan J. Altschuler and Konstantin Tikhomirov, paper authors
- Scope
- Original O(√n), T=n online prefix Spencer proof and the expanded manuscript proofs
- Basis
- Reported by the linked checker
Checking a formal statement does not establish that it matches the original problem.
Human understanding
The human authors explain and rewrite the stationary walk, triplet coupling and bump-law analysis behind the result.
Correction and publication history
Resolves the online Spencer question and improves online sparse Beck–Fiala discrepancy bounds.
Read this published revision