← All problems

Kulkarni–Reis–Rothvoss conjecture for online carpooling

For every n,T≥2n,T\ge 2 and every fixed sequence of unordered edges e1,…,eTe_1,\ldots,e_T on the vertex set [n][n], there exists a randomized online algorithm that orients each edge ete_t immediately upon arrival such that, with probability at least 1−T−c1-T^{-c} for a universal constant c>0c>0, every vertex v∈[n]v\in[n] and every prefix 1≤t≤T1\le t\le T satisfy ∣indeg⁡t(v)−outdeg⁡t(v)∣≤Clog⁡T\left|\operatorname{indeg}_{t}(v)-\operatorname{outdeg}_{t}(v)\right|\le C\sqrt{\log T}, where C>0C>0 is universal.

References

Progress summary

Refreshed
Open · solution reported

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 O(log⁡T)O(\sqrt{\log T}) 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 O(log⁡T)O(\sqrt{\log T}) prefix discrepancy, plus a matching Ω(log⁡T)\Omega(\sqrt{\log T}) 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 O((log⁡T)1/2)O((\log T)^{1/2}) and Ω((log⁡T)1/3)\Omega((\log T)^{1/3}) 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 O(log⁡T)O(\sqrt{\log T}) 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.

Sources

Solutions 0

No solutions have been posted yet.