Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds

DOI10.1145/3188745.3188790zbMATH Open1428.68132arXiv1703.03575OpenAlexW2604958820MaRDI QIDQ5230355FDOQ5230355

Authors: Kasper Green Larsen, O. Weinstein, Huacheng Yu 

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $ildeOmega(lo{g}^{1.5}n)$ lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over $mathbb{F}_2$ ([Pat07]). Proving an $omega(lgn)$ lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Pv{a}trac{s}cu's obituary [Tho13]. This result also implies the first $omega(lgn)$ lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-boolean) problems of range selection and range median. Our technical centerpiece is a new way of "weakly" simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebychev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the "cell sampling" method of Panigrahy et al. [PTW10].

Full work available at URL: https://arxiv.org/abs/1703.03575

Recommendations

• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
• The cell probe complexity of dynamic range counting
• Logarithmic Lower Bounds in the Cell-Probe Model
• Cell-probe lower bounds from online communication complexity
• On dynamic bit-probe complexity

zbMATH Keywords

computational complexitylower boundscommunication complexitycell-probe models

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication complexity, information complexity (68Q11)

Cited In (9)

• The cell probe complexity of dynamic range counting
• Lower bounds for matrix factorization
• Lower bounds for matrix factorization
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Polynomial data structure lower bounds in the group model
• A logarithmic lower bound for oblivious RAM (for all Parameters)
• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
• Title not available (Why is that?)
• Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model

This page was built for publication: Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230355)