Deque conjecture for splay trees

A double-ended queue supports insertions and removals at both ends. Tarjan asked whether a splay tree can perform any sequence of these operations at constant amortized cost.

Why it matters and what counts as progress

Why it matters: The bound improves a longstanding sequence of amortized analyses of splay trees used as double-ended queues.

What counts as progress: Sharper bounds should state how total rotations depend on the number of operations and the initial size of the tree.

How the problem developed

  1. 1985 · Development [1]

    Robert Tarjan Posed the constant-amortized-cost deque conjecture for splay trees.

  2. 13 Nov 2026 · Proof [2][3][4]

    Vahab Mirrokni and colleagues Proved a rotation bound whose overhead grows more slowly than every fixed finite inverse-Ackermann iteration.

AI contribution

Breaking All Iterated Inverse-Ackermann Bounds for the Deque Conjecture on Splay Trees

Vahab Mirrokni, David P. Woodruff, Sorrachai Yingchareonthawornchai, Goran Zuzic

The paper bounds the number of splay rotations used by m deque operations starting with n keys by O((m+n)αω(m+n))O((m+n)\alpha \omega (m+n)). Its ordinal inverse-Ackermann factor grows more slowly than every fixed finite iteration of the usual inverse-Ackermann function.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

Sources

  1. Tarjan’s original splay-tree paper and deque conjecture
  2. Original manuscript
  3. Manuscript AI disclosure
  4. Lean proof of the two main statements
Publication history