{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:21:14Z","timestamp":1771485674149,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451038","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"570-583","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Almost optimal super-constant-pass streaming lower bounds for reachability"],"prefix":"10.1145","author":[{"given":"Lijie","family":"Chen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gillat","family":"Kol","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dmitry","family":"Paramonov","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raghuvansh R.","family":"Saxena","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study at Princeton, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huacheng","family":"Yu","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808726"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Josh Alman and Virginia Vassilevska Williams. 2021. A Refined Laser Method and Faster Matrix Multiplication. In SODA. https:\/\/arxiv.org\/pdf\/2010.05846.pdf.","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316361"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.48"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319697"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897576"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.113"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/FOCS46700.2020.00041"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/FOCS46700.2020.00040"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294402"},{"key":"e_1_3_2_1_11_1","first-page":"1","article-title":"Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models","volume":"91","author":"Becker Ruben","year":"2017","unstructured":"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\u20137:16.","journal-title":"DISC"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897646"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Marc Bury and Chris Schwiegelshohn. 2015. Sublinear estimation of weighted matchings in dynamic data streams. In ESA. 263\u2013274.","DOI":"10.1007\/978-3-662-48350-3_23"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.109"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch94"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1275-6"},{"key":"e_1_3_2_1_18_1","unstructured":"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."},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms (SODA). SIAM, 1234\u20131251","author":"Chitnis Rajesh","year":"2014","unstructured":"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\u20131251."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536445"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_3_2_1_22_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Cormode Graham","year":"2019","unstructured":"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."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167272"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795295948"},{"key":"e_1_3_2_1_25_1","volume-title":"International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Emek Yuval","unstructured":"Yuval Emek and Adi Ros\u00e9n. 2014. Semi-Streaming Set Cover. In International Colloquium on Automata, Languages, and Programming (ICALP). Springer, 453\u2013464."},{"key":"e_1_3_2_1_26_1","volume-title":"International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Feigenbaum Joan","unstructured":"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\u2013543."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331603"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.41"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384248"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Mika Goos Toniann Pitassi and Thomas Watson. 2017. Query-to-Communication Lifting for BPP. In FOCS.","DOI":"10.1109\/FOCS.2017.21"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0138-7"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902287"},{"key":"e_1_3_2_1_36_1","volume-title":"Computing on data streams. External memory algorithms 50","author":"Henzinger Monika Rauch","year":"1998","unstructured":"Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. 1998. Computing on data streams. External memory algorithms 50 (1998), 107\u2013118."},{"key":"e_1_3_2_1_37_1","volume-title":"53rd Annual ACM Symposium on Theory of Computing (STOC). arXiv preprint arXiv:2004","author":"Jiang Shunhua","year":"2021","unstructured":"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."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.121"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897581"},{"key":"e_1_3_2_1_40_1","volume-title":"Breaking the $ n $-Pass Barrier: A Streaming Algorithm for Maximum Weight Bipartite Matching. arXiv preprint arXiv:2009.06106","author":"Liu S Cliff","year":"2020","unstructured":"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)."},{"key":"e_1_3_2_1_41_1","volume-title":"Matching theory","author":"Lov\u00e1sz L\u00e1szl\u00f3","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Michael D Plummer. 2009. Matching theory. Vol. 367. American Mathematical Soc."},{"key":"e_1_3_2_1_42_1","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"McGregor Andrew","unstructured":"Andrew McGregor. 2005. Finding graph matchings in data streams. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer, 170\u2013181."},{"key":"e_1_3_2_1_43_1","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press. isbn:0-521-47465-5"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384334"},{"key":"e_1_3_2_1_45_1","volume-title":"OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science (FOCS)","author":"Nelson Jelani","year":"2013","unstructured":"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\u2013126."},{"key":"e_1_3_2_1_46_1","volume-title":"9th Innovations in Theoretical Computer Science (ITCS). Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH","author":"Rubinstein Aviad","unstructured":"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."},{"key":"e_1_3_2_1_47_1","first-page":"939","article-title":"Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976)","volume":"18","author":"Ruzsa Imre Z","year":"1978","unstructured":"Imre Z Ruzsa and Endre Szemer\u00e9di. 1978. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18 (1978), 939\u2013945.","journal-title":"Coll. Math. Soc. J. Bolyai"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055431"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.10.017"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451038","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":49,"alternative-id":["10.1145\/3406325.3451038","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451038","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}