Pith.

Data Structures and Algorithms · arXiv:2603.10244 v2 · submitted 10 Mar 2026

Transposition Is Nearly Optimal for IID List Update

Christian Coester

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

Pith says

Pith has not reviewed this paper.

Get a Pith Review, $5

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.

Request a human review

How Pith checks papers · The full audit of this paper

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.

SentenceRoleThe authors' own workStates the main conclusionStrength
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

  1. 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

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

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.

No comments yet.

Sign in to comment