Always-Correct Succinct Dynamic Fusion Nodes Are Impossible: A Cell-Probe Lower Bound in the Small-Set, Large-Universe Regime
TL;DR
Lean 4 checks the complete packed-memory and fresh-random indexed models, hard distribution, communication bounds, separator, nested-forest accounting, deterministic and Las Vegas lower bounds, strict-predecessor reduction, and redundancy corollaries.
Abstract
Kuszmaul, Liang, and Zhou (SODA 2026) ask whether succinct constant-time dynamic fusion nodes exist when the number of stored keys is polylogarithmic in the universe size. We give a negative answer for always-correct structures. For n^8<= U, log_2 U>= 2^70, and redundancy 0<= R<n, a dynamic dictionary requires at least 2^-26 log_2(1+n/(R+1)) expected-amortized cell probes per operation. The model permits fixed layouts of packed cells of at most one word each, including the short-spill convention used by succinct word-RAM structures, and covers zero-error Las Vegas algorithms with fresh per-invocation randomness and almost-sure termination. The proof repairs a conditioning defect in the inherited communication argument by placing pointwise probe caps inside the consistency event, then extends the lower bound to large universes through a scale-adaptive entropy parameter. Consequently, when U=2^w and n=ceil(w^c) for any fixed c>0, no always-correct predecessor structure can use log_2 binom(U,n)+o(n) persistent mutable bits and support constant-time operations. Constant expected-amortized time requires Omega(n) redundant bits. Lean 4 checks the complete packed-memory and fresh-random indexed models, hard distribution, communication bounds, separator, nested-forest accounting, deterministic and Las Vegas lower bounds, strict-predecessor reduction, and redundancy corollaries.