Cell-Probe lower bounds from online communication complexity

Josh Alman, Joshua R. Wang, Huacheng Yu

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

2 Scopus citations

Abstract

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players, Bob, his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result each time before the next piece is revealed to Bob. This model has a closer and more natural correspondence to dynamic data structures than classic communication models do, and hence presents a new perspective on data structures. We first present a tight lower bound for the online set intersection problem in the online communication model, demonstrating a general approach for proving online communication lower bounds. The online communication model prevents a batching trick that classic communication complexity allows, and yields a stronger lower bound. We then apply the online communication model to prove data structure lower bounds for two dynamic data structure problems: the Group Range problem and the Dynamic Connectivity problem for forests. Both of the problems admit a worst case O(log n)-time data structure. Using online communication complexity, we prove a tight cell-probe lower bound for each: spending o(log n) (even amortized) time per operation results in at best an exp(− 2n) probability of correctly answering a (1/2 +)-fraction of the n queries.

Original languageEnglish (US)
Title of host publicationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
EditorsMonika Henzinger, David Kempe, Ilias Diakonikolas
PublisherAssociation for Computing Machinery
Pages239-252
Number of pages14
ISBN (Electronic)9781450355599
DOIs
StatePublished - Jun 20 2018
Externally publishedYes
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: Jun 25 2018Jun 29 2018

Publication series

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

Other

Other50th Annual ACM Symposium on Theory of Computing, STOC 2018
Country/TerritoryUnited States
CityLos Angeles
Period6/25/186/29/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Cell-probe model
  • Data structure lower bounds
  • Online communication complexity

Fingerprint

Dive into the research topics of 'Cell-Probe lower bounds from online communication complexity'. Together they form a unique fingerprint.

Cite this