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
AI contribution
Breaking All Iterated Inverse-Ackermann Bounds for the Deque Conjecture on Splay Trees
The paper bounds the number of splay rotations used by m deque operations starting with n keys by . Its ordinal inverse-Ackermann factor grows more slowly than every fixed finite iteration of the usual inverse-Ackermann function.
Sources
Publication history
Breaking All Iterated Inverse-Ackermann Bounds for the Deque Conjecture on Splay Trees
Daily emails by default, only when there’s an update.