Data Structures and Algorithms · arXiv:2603.10244 v2 · submitted 10 Mar 2026
Transposition Is Nearly Optimal for IID List Update
The paper says
“We show that for all distributions, Transposition has stationary expected access cost at most OPT + 1, confirming Rivest's conjecture up to an unavoidable additive constant, and showing near-optimality even among algorithms with memory.”
from the abstract · picked out as the main claim by a classifier
Reviews
Reviews by people
No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
The list update problem is one of the oldest and simplest problems in online algorithms: A set of items must be maintained in a list while requests to these items arrive over time. Whenever an item is requested, the algorithm pays a cost equal to the position of the item in the list. In the i.i.d. model, where requests are drawn independently from a fixed distribution, the static ordering by decreasing access probabilities p1 ≥ p2 ≥ … ≥ pn achieves the minimal expected access cost OPT = ∑i = 1nipi. However, p is typically unknown, and approximating it by tracking access frequencies creates undesirable overheads. A 50-year old conjecture by Rivest states that the Transposition rule (swap the requested item with its predecessor) is optimal among memoryless algorithms. While known to be false in the strict sense, prior research provided asymptotic confirmation of Rivest's conjecture for restricted distributions. We show that for all distributions, Transposition has stationary expected access cost at most OPT + 1, confirming Rivest's conjecture up to an unavoidable additive constant, and showing near-optimality even among algorithms with memory. More abstractly, it yields a purely memoryless procedure to approximately sort probabilities via sampling.
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-11-11 · no language-model review
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.10 · states limitation 0.73 · human participants 0.01 · controlled comparison 0.20 · randomized assignment 0.03 · states quantitative result 0.98 · compares with prior results 0.96 · mentions code or data availability 0.02
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v2). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| The list update problem is one of the oldest and simplest problems in online algorithms: A set of items must be maintained in a list while requests to these items arrive over time. | background 1.00 | 0.03 | 0.01 | asserted 1.00 |
| Whenever an item is requested, the algorithm pays a cost equal to the position of the item in the list. | background 1.00 | 0.04 | 0.01 | asserted 1.00 |
| In the i.i.d. model, where requests are drawn independently from a fixed distribution, the static ordering by decreasing access probabilities $p_1\ge p_2\ge \dots \ge p_n$ achieves the minimal expected access cost $\mathrm{OPT}=\sum_{i=1}^n ip_i$. | background 1.00 | 0.07 | 0.03 | asserted 1.00 |
| However, $p$ is typically unknown, and approximating it by tracking access frequencies creates undesirable overheads. | gap 0.52 | 0.06 | 0.01 | asserted 0.93 |
| A 50-year old conjecture by Rivest states that the Transposition rule (swap the requested item with its predecessor) is optimal among memoryless algorithms. | background 0.96 | 0.03 | 0.03 | speculative 0.59 |
| While known to be false in the strict sense, prior research provided asymptotic confirmation of Rivest's conjecture for restricted distributions. | background 0.83 | 0.04 | 0.03 | asserted 1.00 |
| We show that for all distributions, Transposition has stationary expected access cost at most $\mathrm{OPT}+1$, confirming Rivest's conjecture up to an unavoidable additive constant, and showing near-optimality even among algorithms with memory. | result 0.90 | 0.96 | 0.96 | asserted 1.00 |
| More abstractly, it yields a purely memoryless procedure to approximately sort probabilities via sampling. | interpretation 1.00 | 0.79 | 0.06 | asserted 0.98 |
What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00
What was examined, and what was not
Sources read
- arXiv listing abstract v2
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-11: 1 request, 6,391 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
Cited by 1 Pith paper
Reviewed papers on Pith that cite this one. The full citation record
- List Update with Time Windows and Delays without Batch-Serving cs.DS · Nov 2026
How the literature uses it
1 arXiv paper cite this in 1 sentence
Papers citing it
Cites it as support 1 paper
-
Researchers in mathematics, computer science, and theoretical physics have found modern AI systems useful in the wild, for developing proofs and providing high level reasoning to aid their work [ref] .
Artificial Intelligence and the Structure of Mathematics · Introduction · 0.97
Challenges and discussion
Know something about this paper? Leave a comment.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment