Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Links

DOI

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 approach and use it to prove a Ω (lg 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 F 2 (Pǎtraşcu, 2007). Proving an (lg n) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Pǎtraşcu’s obituary (Thorup, 2013). This result also implies the first (lg n) 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 (Chebyshev) polynomials which May be of independent interest, and offers an entirely new algorithmic angle on the “cell sampling" method of Panigrahy et al. (2010).

Original languageEnglish
Title of host publicationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
EditorsMonika Henzinger, David Kempe, Ilias Diakonikolas
Number of pages12
Place of publicationNew York, NY, USA
PublisherAssociation for Computing Machinery
Publication year20 Jun 2018
Pages978-989
ISBN (print)978-1-4503-5559-9
ISBN (Electronic)9781450355599
DOIs
Publication statusPublished - 20 Jun 2018
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: 25 Jun 201829 Jun 2018

Conference

Conference50th Annual ACM Symposium on Theory of Computing, STOC 2018
LandUnited States
ByLos Angeles
Periode25/06/201829/06/2018
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT)
SeriesA C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings
Number2018
ISSN1055-6338

    Research areas

  • Cell probe complexity, Data structures, Dynamic problems, Lower bounds, Range searching, CELL PROBE COMPLEXITY, Dynamic Problems, Data Structures, Range Searching, Cell Probe Complexity, Lower Bounds

See relations at Aarhus University Citationformats

ID: 132363655