Efficient online discrepancy for Euclidean-unit vectors
Follow the latest progress by email.
For a sequence of T Euclidean unit vectors in Rᵈ fixed before an online signing algorithm runs, seek signs whose every prefix has ℓ∞ discrepancy at most √(18 log(2T²/δ)) with probability at least 1−δ, in O(dT) time.
Why it matters and what counts as progress
Why it matters: It asks whether near-optimal prefix balance can be maintained at runtime linear in the input size against obliviously fixed vectors.
What counts as progress: Improve the prefix discrepancy or failure-probability bound while keeping runtime linear in input size and the input sequence fixed in advance.
How the problem developed
- 2024 · Bound [1]
Janardhan Kulkarni, Victor Reis, and Thomas Rothvoss Proved the optimal O(√log T) online prefix-discrepancy bound, using an algorithm exponential in the sequence length and dimension.
- 5 Jul 2026 · Algorithm [2]
Ishaq Aden-Ali, with GPT-5.5 Pro Extended The preprint gives a randomized O(dT)-time algorithm achieving the same O(√log T) prefix discrepancy with high probability for vectors of Euclidean norm at most one.
AI contribution
Optimal Online Discrepancy Minimization in Linear Time
For every fixed-in-advance sequence of T Euclidean unit vectors in dimension d, Aden-Ali’s Gaussian triplet walk assigns signs in O(dT) time. With probability at least 1−δ, every prefix has ℓ∞ discrepancy at most sqrt(18 log(2T²/δ)).
Sources
Website timeline
Publication dates and editorial changes.