Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-156 | 22nd October 2025 02:27

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

RSS-Feed




TR25-156
Authors: Young Kun Ko
Publication: 22nd October 2025 14:41
Downloads: 32
Keywords: 


Abstract:

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, \ldots, 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), the above explicit dynamic cell-probe problem must have $\max \{ t_u, t_q \} \geq \tilde{\Omega}(\log^{3/2}(n))$ if $m = \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.



ISSN 1433-8092 | Imprint