2025/10/20 by Young Kun Ko, Ko, Young Kun
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Single-cell and spatial transcriptomics
paper · pdf · doi:10.48550/arxiv.2510.17717
openalex publication_date 2025/10/20 · openalex created_date 2025/10/22 · openalex updated_date 2026/07/28
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. S1, …, Sm ∈ \0, 1\n are given and publicly known. 2. T ∈ \0, 1\n is a sequence of updates, each taking tu time. 3. For a given Q ∈ [m], we must output f(SQ, T) in tq 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 SQ and T (for example, a uniform distribution), then the above explicit dynamic cell-probe problem must have max \ tu, tq \ ≥ Ω(log3/2(n)) if m = Ω(n0.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 SQ 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.