{"ID":2852882,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.17717","arxiv_id":"2510.17717","title":"Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds","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), then the above explicit dynamic cell-probe problem must have $\\max \\{ t_u, t_q \\} \\geq \\tildeΩ(\\log^{3/2}(n))$ if $m = Ω(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.","short_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...","url_abs":"https://arxiv.org/abs/2510.17717","url_pdf":"https://arxiv.org/pdf/2510.17717v1","authors":"[\"Young Kun Ko\"]","published":"2025-10-20T16:34:07Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}