TY - GEN
T1 - Near-quadratic lower bounds for two-pass graph streaming algorithms
AU - Assadi, Sepehr
AU - Raz, Ran
N1 - Funding Information:
Sepehr Assadi done part of this project while at Princeton University and was supported in part by the Simons Collaboration on Algorithms and Geometry. Ran Raz was partially supported by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award, and by the National Science Foundation grants No. CCF-171477 and CCF-2007462.
Publisher Copyright:
© 2020 IEEE.
PY - 2020/11
Y1 - 2020/11
N2 - We prove that any two-pass graph streaming algorithm for the s-t reachability problem in n-vertex directed graphs requires near-quadratic space of n{2-o(1)} bits. As a corollary, we also obtain near-quadratic space lower bounds for several other fundamental problems including maximum bipartite matching and (approximate) shortest path in undirected graphs. Our results collectively imply that a wide range of graph problems admit essentially no non-trivial streaming algorithm even when two passes over the input is allowed. Prior to our work, such impossibility results were only known for single-pass streaming algorithms, and the best two-pass lower bounds only ruled out o(n{7/6}) space algorithms, leaving open a large gap between (trivial) upper bounds and lower bounds.
AB - We prove that any two-pass graph streaming algorithm for the s-t reachability problem in n-vertex directed graphs requires near-quadratic space of n{2-o(1)} bits. As a corollary, we also obtain near-quadratic space lower bounds for several other fundamental problems including maximum bipartite matching and (approximate) shortest path in undirected graphs. Our results collectively imply that a wide range of graph problems admit essentially no non-trivial streaming algorithm even when two passes over the input is allowed. Prior to our work, such impossibility results were only known for single-pass streaming algorithms, and the best two-pass lower bounds only ruled out o(n{7/6}) space algorithms, leaving open a large gap between (trivial) upper bounds and lower bounds.
KW - Graph streaming
KW - communication complexity
KW - multi pass streaming lower bounds
KW - s-t reachability
UR - http://www.scopus.com/inward/record.url?scp=85100354753&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85100354753&partnerID=8YFLogxK
U2 - 10.1109/FOCS46700.2020.00040
DO - 10.1109/FOCS46700.2020.00040
M3 - Conference contribution
AN - SCOPUS:85100354753
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 342
EP - 353
BT - Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PB - IEEE Computer Society
T2 - 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
Y2 - 16 November 2020 through 19 November 2020
ER -