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.

What was already known

The deque conjecture asks for constant amortized cost. Earlier analyses still incurred a fixed inverse-Ackermann-type factor.

AI involvement AI-led

The authors credit Gemini 4 Carbon with discovering the proof under light guidance from Zuzic, Woodruff and Mirrokni. Zuzic and Yingchareonthawornchai edited the manuscript. Zuzic, Woodruff and Mirrokni prepared the Lean check.

Importance Notable

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

Technical verification Formal (Lean)

The repository identifies the precise declarations for the main bound, its auxiliary theorems and its standalone statement.

Formal checking

Checked the main rotation bound and the equivalence of the standalone and project specifications.

Checker
Lean 4 kernel
Scope
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.
Basis
Reported by the linked checker

Human understanding Few

The disclosure identifies who guided the model, edited the paper and prepared Lean. It leaves a human reconstruction of the model’s main contraction argument undocumented.

Other useful sources

Correction and publication history