The Arborescence-Sampling Barrier for Eulerian Tours
Sampling a nearly uniform Eulerian tour of a directed Eulerian multigraph was stuck at -type running times coming from arborescence sampling. A randomized algorithm achieves worst case, breaking that barrier on sparse graphs.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Randomized algorithms
- Posed by
- arborescence-sampling literature
- Year posed
- —
- Years open
- —
- Solved
- 2026-05-28
- Model
- GPT-5.5 Pro Extended, Codex
- Vendor
- OpenAI
- Collaborators
- Nima Anari
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
A clean division of labour, stated as such: the author conjectured the mixing theorem underlying the analysis, and GPT-5.5 Pro Extended produced its linear-algebra proof. Codex assisted with manuscript assembly.
Verification
Single-author arXiv preprint; not yet peer-reviewed.
Source
arXiv:2605.29566 - Sampling Directed Eulerian Tours in O(m^{3/2}) Time