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.
simplified the simulation protocol and its analysis; Theorem 1.1 now also states the bound on max{t_u, t_tot}; fixed and simplified the proof of the general lifting theorem (Theorem B.3), which now conditions on the transcripts of a random subset of queries; the hardness condition (Definition B.1) is essentially unchanged; added references (Viola's Open Question 15.24; the natural proofs barrier of Koucky, Loff, Molli and Saks; Jain, Radhakrishnan and Sen for Claim 2.16); editorial revisions throughout
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 celebrated barrier for weighted problems established by Larsen [STOC 2012] and closes the gap left by the $\Omega(\log^{1.5} n)$ Boolean bound of Larsen, Weinstein, and Yu [STOC 2018].
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 allows us to bypass technical barriers and obtain the optimal bound directly. As a consequence, our analysis naturally extends to other hard Boolean functions, 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.
