An $\Omega ((\log n/\log \log n{)}^2)$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures

Abstract

We resolve the long-standing open problem of Boolean dynamic data structure hardness, proving an unconditional lower bound of $\Omega ((\log n/\log \log n{)}^2)$ for the Multiphase Problem of Patrascu [STOC 2010] (instantiated with Inner Product over ${\mathbb{F}}_2$). This matches the $\tilde{\Omega }({\log }^{2}n)$ bound that Larsen [STOC 2012] established for weighted problems, where each query returns $\Omega (\log n)$ bits, and closes the gap left by the $\tilde{\Omega }({\log }^{1.5}n)$ Boolean bound of Larsen, Weinstein, and Yu [STOC 2018]. It also answers, up to a $(\log \log n{)}^2$ factor, Open Question 15.24 in Viola's textbook "Mathematics of the Impossible" [Cambridge 2026]. The previous barrier was methodological: all prior works relied on "one-way" communication games, where the inability to verify query simulations necessitated complex machinery (such as the Peak-to-Average Lemma) that hit a hard ceiling at ${\log }^{1.5}n$. Our key contribution is conceptual: we introduce a 2.5-round Multiphase Communication Game that augments the standard one-way model with a verification round, where Bob confirms the consistency of Alice's simulation against the actual memory. This simple, qualitative change removes the obstruction and yields the full bound directly. As a consequence, our analysis naturally extends to other hard Boolean functions -- those of small discrepancy under product distributions with large min-entropy -- offering a general recipe for translating discrepancy lower bounds into $\Omega ((\log n/\log \log n{)}^2)$ dynamic Boolean data structure lower bounds. We also argue that this result likely represents the structural ceiling of the Chronogram framework initiated by Fredman and Saks [STOC 1989]: any $\omega ({\log }^{2}n)$ lower bound would require either fundamentally new techniques or major circuit complexity breakthroughs.

36 pages, 3 figures. Full version of a paper to appear in the Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS 2026). This version: fixed and simplified the proof of the general lifting theorem (Theorem B.3); simplified the simulation argument; added references; editorial revisions