Kulkarni–Reis–Rothvoss conjecture for online carpooling
For every and every fixed sequence of unordered edges on the vertex set , there exists a randomized online algorithm that orients each edge immediately upon arrival such that, with probability at least for a universal constant , every vertex and every prefix satisfy , where is universal.
References
- Online carpooling against an oblivious adversary — arXiv — Yuhao Lei
Source: arXiv
Progress summary
A June 2026 preprint claims to achieve the conjectured optimal discrepancy scale, but the proof has not been independently assessed.
The Kulkarni–Reis–Rothvoss conjecture predicts the optimal discrepancy scale for online carpooling and related online vector balancing. Their earlier work established this scale existentially, but not with an efficient algorithm.
Known results
- Kulkarni, Reis, and Rothvoss (2023; STOC 2024): an online algorithm with prefix discrepancy, plus a matching lower bound against an oblivious adversary, but no efficient implementation.
- Bansal et al. (2020): an efficient polylogarithmic bound for independently sampled edges, a stochastic model rather than the worst-case conjecture.
- Later work records a remaining gap between and in a stochastic general-graph setting.
June 27, 2026 claimed solution
Ishaq Aden-Ali’s preprint claims a linear-time Gaussian-triplet-walk algorithm achieving discrepancy with high probability for every fixed input sequence, thereby matching the lower bound. It states that the algorithm and main proof were discovered by OpenAI’s GPT-5.5 Pro Extended reasoning model, then verified and rewritten by the author; no independent mathematical assessment was found.
Current status (as of November 2026): The conjectured scale is claimed achieved, but the claimed resolution remains unverified and should be treated as open pending independent assessment.
Solutions 0
No solutions have been posted yet.