Cell-probe lower bounds for dynamic problems via a new communication model

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

In this paper, we develop a new communication model to prove a data structure lower bound for the dynamic interval union problem. The problem is to maintain a multiset of intervals I over [0,n] with integer coordinates, supporting the following operations: 1) insert(a, b), add an interval [a, b] to I, provided that a and b are integers in [0,n]; 2) delete(a, b), delete an (existing) interval [a, b] from I; 3) query(), return the total length of the union of all intervals in I. It is related to the two-dimensional case of Klee's measure problem. We prove that there is a distribution over sequences of operations with O(n) insertions and deletions, and O(n0.01) queries, for which any data structure with any constant error probability requires Ω(nlogn) time in expectation. Interestingly, we use the sparse set disjointness protocol of Håstad and Wigderson to speed up a reduction from a new kind of nondeterministic communication games, for which we prove lower bounds. For applications, we prove lower bounds for several dynamic graph problems by reducing them from dynamic interval union.

Original languageEnglish (US)
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
EditorsYishay Mansour, Daniel Wichs
PublisherAssociation for Computing Machinery
Pages362-374
Number of pages13
ISBN (Electronic)9781450341325
DOIs
StatePublished - Jun 19 2016
Externally publishedYes
Event48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States
Duration: Jun 19 2016Jun 21 2016

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume19-21-June-2016
ISSN (Print)0737-8017

Other

Other48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
Country/TerritoryUnited States
CityCambridge
Period6/19/166/21/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Cell-probe model
  • Klee's measure problem
  • Lower bound

Fingerprint

Dive into the research topics of 'Cell-probe lower bounds for dynamic problems via a new communication model'. Together they form a unique fingerprint.

Cite this