TY - GEN

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

AU - Chen, Lijie

AU - Kol, Gillat

AU - Paramonov, Dmitry

AU - Saxena, Raghuvansh R.

AU - Song, Zhao

AU - Yu, Huacheng

N1 - Funding Information:
Lijie Chen is supported by an IBM Fellowship. Zhao Song is supported in part by Ma Huateng Foundation, Schmidt Foundation, Simons Foundation, NSF, DARPA/SRC, Google and Amazon AWS.
Publisher Copyright:
© 2021 ACM.

PY - 2021/6/15

Y1 - 2021/6/15

N2 - 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.

AB - 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.

KW - Communication Complexity

KW - Graph Streaming

KW - Lower Bounds

UR - http://www.scopus.com/inward/record.url?scp=85108144807&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108144807&partnerID=8YFLogxK

U2 - 10.1145/3406325.3451038

DO - 10.1145/3406325.3451038

M3 - Conference contribution

AN - SCOPUS:85108144807

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 570

EP - 583

BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Khuller, Samir

A2 - Williams, Virginia Vassilevska

PB - Association for Computing Machinery

T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021

Y2 - 21 June 2021 through 25 June 2021

ER -