What was already known
Kulkarni, Reis and Rothvoss obtained an essentially optimal O(sqrt(log T)) prefix bound with a procedure exponential in T and d.
AI involvement
GPT-5.5 Pro Extended proposed the three-walk algorithm and main proof under Aden-Ali’s prompts. Aden-Ali verified and rewrote the proof and derived its discrepancy consequences.
The model supplied the algorithm and main proof under iterative human prompting; the disclosure does not establish near-zero human mathematical direction.
Importance
Keeps the near-optimal discrepancy order while reducing runtime to linear in input size.
Limitations
The vectors must be fixed before the randomized run; an adaptive adversary is outside the claim. Aden-Ali reports verifying and rewriting the model proof; no machine check is documented.
Technical verification
The author explicitly reports verifying and rewriting the complete main proof. This is a source-reported human proof check of the fixed-sequence Gaussian-triplet theorem; no proof-assistant check is documented.
Formal checking
Manual verification and rewrite of the model's self-contained proof
- Checker
- Ishaq Aden-Ali
- Scope
- The Gaussian triplet walk's main theorem for every fixed sequence of ℓ₂-unit vectors and O(dT) runtime
- Basis
- Reported by the linked checker
Checking a formal statement does not establish that it matches the original problem.
Human understanding
Aden-Ali rewrote the proof and explains the three-walk coupling, preserved Gaussian marginals and discrepancy consequence.
Correction and publication history
Keeps the near-optimal discrepancy order while reducing runtime to linear in input size.
Read this published revision