Transposition is Nearly Optimal for IID List Update
In the list update problem, is the simple transposition rule optimal under IID requests? The question traces to Rivest's 1976 study of self-organizing lists. The paper proves transposition is within a small constant factor of the optimal online algorithm under any IID distribution.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI-assisted
- Method
- Argument
- Field
- Online algorithms
- Posed by
- Ronald Rivest (transposition heuristic)
- Year posed
- 1976
- Years open
- 50y
- Solved
- 2026-03-10
- Model
- GPT-5 Pro
- Vendor
- OpenAI
- Collaborators
- Christian Coester
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
"The AI generated the idea that the inequality might hold, and hypothesized, based on experiments with small n, that coefficients of the corresponding polynomial appear to be nonnegative. Although the AI was unable to prove these statements... these suggestions were essential for motivating the proof approach pursued in this paper."