Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds

We prove a general translation theorem for converting one-way communication lower bounds over a product distribution to dynamic cell-probe lower bounds. Specifically, we consider a class of problems considered in [Pat10] where: 1. $S_1,\dots ,S_m\in \{0,1{\}}^n$ are given and publicly known. 2. $T\in \{0,1{\}}^n$ is a sequence of updates, each taking $t_u$ time. 3. For a given $Q\in [m]$, we must output $f(S_Q,T)$ in $t_q$ time. Our main result shows that for a “hard” function $f$, for which it is difficult to obtain a non-trivial advantage over random guessing with one-way communication under some product distribution over $S_Q$ and $T$ (for example, a uniform distribution), then the above explicit dynamic cell-probe problem must have $\max \{t_u,t_q\}\ge \tilde{\mathrm{\Omega }}({\log }^{3\mathrm{/}2}(n))$ if $m=\mathrm{\Omega }(n^{0.99})$. This result extends and unifies the super-logarithmic dynamic data structure lower bounds from [LWY20] and [LY25] into a more general framework. From a technical perspective, our approach merges the cell-sampling and chronogram techniques developed in [LWY20] and [LY25] with the new static data structure lower bound methods from [KW20] and [Ko25], thereby merging all known state-of-the-art cell-probe lower-bound techniques into one. As a direct consequence of our method, we establish a super-logarithmic lower bound against the Multiphase Problem [Pat10] for the case where the data structure outputs the Inner Product (mod 2) of $S_Q$ and $T$. We suspect further applications of this general method towards showing super-logarithmic dynamic cell-probe lower bounds. We list some example applications of our general method, including a novel technique for a one-way communication lower bound against small-advantage protocols for a product distribution using average min-entropy, which could be of independent interest.