Almost optimal super-constant-pass streaming lower bounds for reachability

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu

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

Abstract

We give an almost quadratic n2-o(1) lower bound on the space consumption of any o(?logn)-pass streaming algorithm solving the (directed) s-t reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including maximum matching, shortest path, matrix rank, and linear programming. Our main technical contribution is the definition and construction of set hiding graphs, that may be of independent interest: we give a general way of encoding a set S ? [k] as a directed graph with n = k 1 + o( 1 ) vertices, such that deciding whether i e S boils down to deciding if ti is reachable from si, for a specific pair of vertices (si,ti) in the graph. Furthermore, we prove that our graph "hides"S, in the sense that no low-space streaming algorithm with a small number of passes can learn (almost) anything about S.

Original languageEnglish (US)
Title of host publicationSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
EditorsSamir Khuller, Virginia Vassilevska Williams
PublisherAssociation for Computing Machinery
Pages570-583
Number of pages14
ISBN (Electronic)9781450380539
DOIs
StatePublished - Jun 15 2021
Event53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy
Duration: Jun 21 2021Jun 25 2021

Publication series

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

Conference

Conference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Country/TerritoryItaly
CityVirtual, Online
Period6/21/216/25/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Communication Complexity
  • Graph Streaming
  • Lower Bounds

Fingerprint

Dive into the research topics of 'Almost optimal super-constant-pass streaming lower bounds for reachability'. Together they form a unique fingerprint.

Cite this