More Web Proxy on the site http://driver.im/

research-article

Open access

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

Authors:

Dmitry Paramonov,

Raghuvansh R. Saxena,

Huacheng YuAuthors Info & Claims

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

Pages 570 - 583

https://doi.org/10.1145/3406325.3451038

Published: 15 June 2021 Publication History

Abstract

We give an almost quadratic n^2−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 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.

References

[1]

Miklós Ajtai, János Komlós, and Endre Szemerédi. 1983. An $O(n łog n)$ sorting network. In Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC). 1–9.

Digital Library

[2]

Josh Alman and Virginia Vassilevska Williams. 2021. A Refined Laser Method and Faster Matrix Multiplication. In SODA. https://arxiv.org/pdf/2010.05846.pdf.

[3]

Sepehr Assadi, Yu Chen, and Sanjeev Khanna. 2019. Polynomial pass lower bounds for graph streaming algorithms. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC). 265–276.

Digital Library

[4]

Sepehr Assadi, Yu Chen, and Sanjeev Khanna. 2019. Sublinear algorithms for ($\Delta$ + 1) vertex coloring. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 767–786.

[5]

Sepehr Assadi, Nikolai Karpov, and Qin Zhang. 2019. Distributed and Streaming Linear Programming in Low Dimensions. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS). ACM, 236–253.

Digital Library

[6]

Sepehr Assadi, Sanjeev Khanna, and Yang Li. 2016. Tight bounds for single-pass streaming complexity of the set cover problem. In 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC). Association for Computing Machinery, 698–711.

Digital Library

[7]

Sepehr Assadi, Sanjeev Khanna, and Yang Li. 2017. On estimating maximum matching size in graph streams. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1723–1742.

[8]

Sepehr Assadi, Gillat Kol, Raghuvansh R Saxena, and Huacheng Yu. 2020. Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. In FOCS. https://arxiv.org/pdf/2009.03038.pdf.

[9]

Sepehr Assadi and Ran Raz. 2020. Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. In FOCS. https://arxiv.org/pdf/2009.01161.pdf.

[10]

Greg Barnes and Jeff A Edmonds. 1998. Time–Space Lower Bounds for Directed st-Connectivity on Graph Automata Models. SIAM J. Comput. 27, 4 (1998), 1190–1202.

Digital Library

[11]

Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In DISC, Vol. 91. 7:1–7:16.

[12]

Felix A. Behrend. 1946. On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences of the United States of America 32, 12 (1946), 331.

[13]

Christos Boutsidis, David P Woodruff, and Peilin Zhong. 2016. Optimal principal component analysis in distributed and streaming models. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (STOC). 236–249.

Digital Library

[14]

Marc Bury and Chris Schwiegelshohn. 2015. Sublinear estimation of weighted matchings in dynamic data streams. In ESA. 263–274.

[15]

Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, and Sofya Vorotnikova. 2020. Vertex ordering problems in directed graph streams. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1786–1802.

[16]

Amit Chakrabarti and Anthony Wirth. 2016. Incidence geometries and the pass complexity of semi-streaming set cover. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA). SIAM, 1365–1373.

[17]

Timothy M. Chan and Eric Y. Chen. 2007. Multi-Pass Geometric Algorithms. Discret. Comput. Geom. 37, 1 (2007), 79–102.

Digital Library

[18]

Yi-Jun Chang, Martin Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai. 2020. Streaming complexity of spanning tree computation, In STACS. arXiv preprint arXiv:2001.07672.

[19]

Rajesh Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, and Morteza Monemizadeh. 2014. Parameterized streaming: Maximal matching and vertex cover. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms (SODA). SIAM, 1234–1251.

[20]

Kenneth L Clarkson and David P Woodruff. 2009. Numerical linear algebra in the streaming model. In Proceedings of the forty-first annual ACM symposium on Theory of computing (STOC). 205–214.

Digital Library

[21]

Kenneth L Clarkson and David P Woodruff. 2013. Low rank approximation and regression in input sparsity time. In Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (STOC). 81–90.

Digital Library

[22]

Graham Cormode, Jacques Dark, and Christian Konrad. 2019. Independent Sets in Vertex-Arrival Streams. In 46th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[23]

Jeff Edmonds. 1993. Time-space trade-offs for undirected st-connectivity on a JAG. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing. 718–727.

Digital Library

[24]

Jeff Edmonds, Chung Keung Poon, and Dimitris Achlioptas. 1999. Tight lower bounds for st-connectivity on the NNJAG model. SIAM J. Comput. 28, 6 (1999), 2257–2284.

Digital Library

[25]

Yuval Emek and Adi Rosén. 2014. Semi-Streaming Set Cover. In International Colloquium on Automata, Languages, and Programming (ICALP). Springer, 453–464.

[26]

Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. 2004. On graph problems in a semi-streaming model. In International Colloquium on Automata, Languages, and Programming (ICALP). Springer, 531–543.

[27]

Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. 2009. Graph distances in the data-stream model. SIAM J. Comput. 38, 5 (2009), 1709–1727.

Digital Library

[28]

Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky. 2002. Monotonicity testing over general poset domains. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (STOC). 474–483.

Digital Library

[29]

Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, and Ola Svensson. 2019. Weighted matchings via unweighted augmentations. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC). 491–500.

Digital Library

[30]

Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld. 2018. Improved massively parallel computation algorithms for mis, matching, and vertex cover. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). 129–138.

Digital Library

[31]

Ashish Goel, Michael Kapralov, and Sanjeev Khanna. 2012. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms (SODA). SIAM, 468–485.

[32]

Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi. 2020. Automating cutting planes is NP-hard. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 68–77.

Digital Library

[33]

Mika Goos, Toniann Pitassi, and Thomas Watson. 2017. Query-to-Communication Lifting for BPP. In FOCS.

[34]

Venkatesan Guruswami and Krzysztof Onak. 2016. Superlinear lower bounds for multipass graph processing. Algorithmica 76, 3 (2016), 654–683.

Digital Library

[35]

Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian. 2016. Towards tight bounds for the streaming set cover problem. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS). 371–383.

Digital Library

[36]

Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. 1998. Computing on data streams. External memory algorithms 50 (1998), 107–118.

[37]

Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. 2021. Faster dynamic matrix inverse for faster lps. In 53rd Annual ACM Symposium on Theory of Computing (STOC). arXiv preprint arXiv:2004.07470.

[38]

Michael Kapralov. 2013. Better bounds for matchings in the streaming model. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms (SODA). SIAM, 1679–1697.

[39]

Yi Li and David P Woodruff. 2016. On approximating functions of the singular values in a stream. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (STOC). 726–739.

Digital Library

[40]

S Cliff Liu, Zhao Song, and Hengjie Zhang. 2020. Breaking the $ n $-Pass Barrier: A Streaming Algorithm for Maximum Weight Bipartite Matching. arXiv preprint arXiv:2009.06106 (2020).

[41]

László Lovász and Michael D Plummer. 2009. Matching theory. Vol. 367. American Mathematical Soc.

[42]

Andrew McGregor. 2005. Finding graph matchings in data streams. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer, 170–181.

[43]

Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press. isbn:0-521-47465-5

Digital Library

[44]

Sagnik Mukhopadhyay and Danupon Nanongkai. 2020. Weighted min-cut: sequential, cut-query, and streaming algorithms. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC). 496–509.

Digital Library

[45]

Jelani Nelson and Huy L Nguy\^en. 2013. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science (FOCS). IEEE, 117–126.

[46]

Aviad Rubinstein, Tselil Schramm, and Seth Matthew Weinberg. 2018. Computing exact minimum cuts without knowing the graph. In 9th Innovations in Theoretical Computer Science (ITCS). Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 39.

[47]

Imre Z Ruzsa and Endre Szemerédi. 1978. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18 (1978), 939–945.

[48]

Zhao Song, David P Woodruff, and Peilin Zhong. 2017. Low rank approximation with entrywise l1-norm error. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC). 688–701.

Digital Library

[49]

Mariano Zelke. 2011. Intractability of min-and max-cut in streaming graphs. Inform. Process. Lett. 111, 3 (2011), 145–150.

Digital Library

Cited By

Arunachalam SDoriguello J(2024)Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet caseACM Transactions on Computation Theory10.1145/368882416:4(1-38)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3688824
Chou CGolovnev ASudan MVelusamy S(2024)Sketching Approximability of All Finite CSPsJournal of the ACM10.1145/364943571:2(1-74)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3649435
Oostveen Jvan Leeuwen E(2024)Parameterized Complexity of Streaming Diameter and Connectivity ProblemsAlgorithmica10.1007/s00453-024-01246-z86:9(2885-2928)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01246-z
Show More Cited By

Index Terms

Almost optimal super-constant-pass streaming lower bounds for reachability
1. Theory of computation
  1. Computational complexity and cryptography
    1. Communication complexity
  2. Models of computation
    1. Streaming models

Recommendations

Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or ...
Polynomial pass lower bounds for graph streaming algorithms
STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

We present new lower bounds that show that a polynomial number of passes are necessary for solving some fundamental graph problems in the streaming model of computation. For instance, we show that any streaming algorithm that finds a weighted minimum s-...
Optimal lower bounds for matching and vertex cover in dynamic graph streams
CCC '20: Proceedings of the 35th Computational Complexity Conference

In this paper, we give simple optimal lower bounds on the one-way two-party communication complexity of approximate Maximum Matching and Minimum Vertex Cover with deletions. In our model, Alice holds a set of edges and sends a single message to Bob. Bob ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

June 2021

1797 pages

ISBN:9781450380539

DOI:10.1145/3406325

General Chair:
Samir Khuller
Northwestern University, USA
,
Program Chair:
Virginia Vassilevska Williams
Massachusetts Institute of Technology, USA

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '21

Sponsor:

SIGACT

STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing

June 21 - 25, 2021

Virtual, Italy

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
586
Total Downloads

Downloads (Last 12 months)147
Downloads (Last 6 weeks)18

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Arunachalam SDoriguello J(2024)Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet caseACM Transactions on Computation Theory10.1145/368882416:4(1-38)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3688824
Chou CGolovnev ASudan MVelusamy S(2024)Sketching Approximability of All Finite CSPsJournal of the ACM10.1145/364943571:2(1-74)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3649435
Oostveen Jvan Leeuwen E(2024)Parameterized Complexity of Streaming Diameter and Connectivity ProblemsAlgorithmica10.1007/s00453-024-01246-z86:9(2885-2928)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01246-z
El Halabi MFusco FNorouzi-Fard ATardos JTarnawski JKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Fairness in streaming submodular maximization over a matroid constraintProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618775(9150-9171)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618775
Assadi S(2023)Recent Advances in Multi-Pass Graph Streaming Lower BoundsACM SIGACT News10.1145/3623800.362380854:3(48-75)Online publication date: 11-Sep-2023
https://dl.acm.org/doi/10.1145/3623800.3623808
Assadi SSundaresan J(2023)Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00058(909-932)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00058
Assadi SKol GZhang Z(2022)Rounds vs Communication Tradeoffs for Maximal Independent Sets2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00115(1193-1204)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00115
Blikstad JVan Den Brand JEfron YMukhopadhyay SNanongkai D(2022)Nearly Optimal Communication and Query Complexity of Bipartite Matching2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00113(1174-1185)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00113

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten