Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR21-027 | 24th February 2021 00:33

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability

TR21-027
Authors: Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Publication: 24th February 2021 04:18
Keywords:

Abstract:

We give an almost quadratic $n^{2-o(1)}$ lower bound on the space consumption of any $o(\sqrt{\log n})$-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 \subseteq [k]$ as a directed graph with $n = k^{ 1 + o( 1 ) }$ vertices, such that deciding whether $i \in S$ boils down to deciding if $t_i$ is reachable from $s_i$, for a specific pair of vertices $(s_i,t_i)$ 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$.

ISSN 1433-8092 | Imprint