Skip to main content

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

Author(s): Chen, Lijie; Kol, Gillat; Paramonov, Dmitry; Saxena, Raghuvansh; Song, Zhao; et al

To refer to this page use:
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 ∈ 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.
Publication Date: 2021
Citation: Chen, Lijie, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. "Almost optimal super-constant-pass streaming lower bounds for reachability." In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021): pp. 570-583. doi:10.1145/3406325.3451038
DOI: 10.1145/3406325.3451038
Pages: 570 - 583
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.