{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:47Z","timestamp":1750219847975,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["NSF CAREER Grant CCF-2047061"],"award-info":[{"award-number":["NSF CAREER Grant CCF-2047061"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","award":["Sloan Research Fellowship"],"award-info":[{"award-number":["Sloan Research Fellowship"]}],"id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Google Research Gift"],"award-info":[{"award-number":["Google Research Gift"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Rutgers Research Council","award":["Fulcrum Award"],"award-info":[{"award-number":["Fulcrum Award"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585192","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"183-195","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond"],"prefix":"10.1145","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"Rutgers University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Janani","family":"Sundaresan","sequence":"additional","affiliation":[{"name":"Rutgers University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_3_2_1_2_1","volume-title":"Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds. In Conference on Learning Theory","volume":"4702","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi , Vaggos Chatziafratis , Jakub Lacki , Vahab Mirrokni , and Chen Wang . 2022 . Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds. In Conference on Learning Theory , 2-5 July 2022, London, UK, Po-Ling Loh and Maxim Raginsky (Eds.) (Proceedings of Machine Learning Research , Vol. 178). PMLR, 4643\u2013 4702 . Sepehr Assadi, Vaggos Chatziafratis, Jakub Lacki, Vahab Mirrokni, and Chen Wang. 2022. Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds. In Conference on Learning Theory, 2-5 July 2022, London, UK, Po-Ling Loh and Maxim Raginsky (Eds.) (Proceedings of Machine Learning Research, Vol. 178). PMLR, 4643\u20134702."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00041"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451110"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007379"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","author":"Braverman Vladimir","year":"2018","unstructured":"Vladimir Braverman , Stephen R. Chestnut , Robert Krauthgamer , Yi Li , David P. Woodruff , and Lin F. Yang . 2018. Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order . In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan , Stockholm, Sweden , July 10-15, 2018 , Jennifer G. Dy and Andreas Krause (Eds.) (Proceedings of Machine Learning Research, Vol. 80). PMLR, 648\u2013657. Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, and Lin F. Yang. 2018. Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10-15, 2018, Jennifer G. Dy and Andreas Krause (Eds.) (Proceedings of Machine Learning Research, Vol. 80). PMLR, 648\u2013657."},{"key":"e_1_3_2_1_7_1","volume-title":"Patras","volume":"274","author":"Bury Marc","year":"2015","unstructured":"Marc Bury and Chris Schwiegelshohn . 2015 . Sublinear Estimation of Weighted Matchings in Dynamic Data Streams. In Algorithms - ESA 2015 - 23rd Annual European Symposium , Patras , Greece, September 14-16, 2015, Proceedings, Nikhil Bansal and Irene Finocchi (Eds.) (Lecture Notes in Computer Science , Vol. 9294). Springer, 263\u2013 274 . Marc Bury and Chris Schwiegelshohn. 2015. Sublinear Estimation of Weighted Matchings in Dynamic Data Streams. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, Nikhil Bansal and Irene Finocchi (Eds.) (Lecture Notes in Computer Science, Vol. 9294). Springer, 263\u2013274."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374470"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993644"},{"key":"e_1_3_2_1_10_1","volume-title":"28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings, Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen (Eds.) (Lecture Notes in Computer Science","volume":"200","author":"Chazelle Bernard","year":"2001","unstructured":"Bernard Chazelle , Ronitt Rubinfeld , and Luca Trevisan . 2001 . Approximating the Minimum Spanning Tree Weight in Sublinear Time. In Automata, Languages and Programming , 28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings, Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen (Eds.) (Lecture Notes in Computer Science , Vol. 2076). Springer, 190\u2013 200 . Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. 2001. Approximating the Minimum Spanning Tree Weight in Sublinear Time. In Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings, Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen (Eds.) (Lecture Notes in Computer Science, Vol. 2076). Springer, 190\u2013200."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch35"},{"key":"e_1_3_2_1_12_1","volume-title":"Factorial Lower Bounds for (Almost) Random Order Streams. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS","author":"Chiplunkar Ashish","year":"2022","unstructured":"Ashish Chiplunkar , John Kallaugher , Michael Kapralov , and Eric Price . 2022 . Factorial Lower Bounds for (Almost) Random Order Streams. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE. Ashish Chiplunkar, John Kallaugher, Michael Kapralov, and Eric Price. 2022. Factorial Lower Bounds for (Almost) Random Order Streams. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE."},{"key":"e_1_3_2_1_13_1","volume-title":"The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs. In 25th Annual European Symposium on Algorithms, ESA 2017","volume":"15","author":"Cormode Graham","year":"2017","unstructured":"Graham Cormode , Hossein Jowhari , Morteza Monemizadeh , and S. Muthukrishnan . 2017 . The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs. In 25th Annual European Symposium on Algorithms, ESA 2017 , September 4-6, 2017 , Vienna, Austria, Kirk Pruhs and Christian Sohler (Eds.) (LIPIcs , Vol. 87). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 29:1\u201329: 15 . Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan. 2017. The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, Kirk Pruhs and Christian Sohler (Eds.) (LIPIcs, Vol. 87). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 29:1\u201329:15."},{"key":"e_1_3_2_1_14_1","volume-title":"Space Complexity. In 24th Annual European Symposium on Algorithms, ESA 2016","volume":"15","author":"Crouch Michael S.","year":"2016","unstructured":"Michael S. Crouch , Andrew McGregor , Gregory Valiant , and David P. Woodruff . 2016. Stochastic Streams: Sample Complexity vs . Space Complexity. In 24th Annual European Symposium on Algorithms, ESA 2016 , August 22-24, 2016 , Aarhus, Denmark, Piotr Sankowski and Christos D. Zaroliagis (Eds.) (LIPIcs , Vol. 57). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 32:1\u201332: 15 . Michael S. Crouch, Andrew McGregor, Gregory Valiant, and David P. Woodruff. 2016. Stochastic Streams: Sample Complexity vs. Space Complexity. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, Piotr Sankowski and Christos D. Zaroliagis (Eds.) (LIPIcs, Vol. 57). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 32:1\u201332:15."},{"key":"e_1_3_2_1_15_1","volume-title":"APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference, Jaroslaw Byrka and Raghu Meka (Eds.) (LIPIcs","volume":"20","author":"Czumaj Artur","year":"2020","unstructured":"Artur Czumaj , Hendrik Fichtenberger , Pan Peng , and Christian Sohler . 2020 . Testable Properties in General Graphs and Random Order Streaming. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference, Jaroslaw Byrka and Raghu Meka (Eds.) (LIPIcs , Vol. 176). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 16:1\u201316: 20 . Artur Czumaj, Hendrik Fichtenberger, Pan Peng, and Christian Sohler. 2020. Testable Properties in General Graphs and Random Order Streaming. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference, Jaroslaw Byrka and Raghu Meka (Eds.) (LIPIcs, Vol. 176). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 16:1\u201316:20."},{"key":"e_1_3_2_1_16_1","volume-title":"Dubhashi and Alessandro Panconesi","author":"Devdatt","year":"2009","unstructured":"Devdatt P. Dubhashi and Alessandro Panconesi . 2009 . Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press . Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.81"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250866"},{"key":"e_1_3_2_1_21_1","volume-title":"APPROX\/RANDOM 2019","volume":"12","author":"Guruswami Venkatesan","year":"2019","unstructured":"Venkatesan Guruswami and Runzhou Tao . 2019 . Streaming Hardness of Unique Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2019 , September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, Dimitris Achlioptas and L\u00e1szl\u00f3 A. V\u00e9gh (Eds.) (LIPIcs , Vol. 145). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 5:1\u20135: 12 . Venkatesan Guruswami and Runzhou Tao. 2019. Streaming Hardness of Unique Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, Dimitris Achlioptas and L\u00e1szl\u00f3 A. V\u00e9gh (Eds.) (LIPIcs, Vol. 145). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 5:1\u20135:12."},{"key":"e_1_3_2_1_22_1","volume-title":"APPROX\/RANDOM 2017, August 16-18","volume":"19","author":"Guruswami Venkatesan","year":"2017","unstructured":"Venkatesan Guruswami , Ameya Velingker , and Santhoshini Velusamy . 2017 . Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2017, August 16-18 , 2017, Berkeley, CA, USA, Klaus Jansen, Jos\u00e9 D. P. Rolim, David Williamson, and Santosh S. Vempala (Eds.) (LIPIcs , Vol. 81). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 8:1\u20138: 19 . Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. 2017. Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, Klaus Jansen, Jos\u00e9 D. P. Rolim, David Williamson, and Santosh S. Vempala (Eds.) (LIPIcs, Vol. 81). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 8:1\u20138:19."},{"key":"e_1_3_2_1_23_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016","volume":"16","author":"Huang Zengfeng","year":"2016","unstructured":"Zengfeng Huang and Pan Peng . 2016 . Dynamic Graph Stream Algorithms in o(n) Space. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 , July 11-15, 2016, Rome, Italy, Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.) (LIPIcs , Vol. 55). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 18:1\u201318: 16 . Zengfeng Huang and Pan Peng. 2016. Dynamic Graph Stream Algorithms in o(n) Space. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.) (LIPIcs, Vol. 55). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 18:1\u201318:16."},{"key":"e_1_3_2_1_24_1","volume-title":"Woodruff","author":"Indyk Piotr","year":"2003","unstructured":"Piotr Indyk and David P . Woodruff . 2003 . Tight Lower Bounds for the Distinct Elements Problem. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings. IEEE Computer Society , 283\u2013288. Piotr Indyk and David P. Woodruff. 2003. Tight Lower Bounds for the Distinct Elements Problem. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings. IEEE Computer Society, 283\u2013288."},{"key":"e_1_3_2_1_25_1","volume-title":"29th Annual Symposium on Foundations of Computer Science","author":"Kahn Jeff","year":"1988","unstructured":"Jeff Kahn , Gil Kalai , and Nathan Linial . 1988 . The Influence of Variables on Boolean Functions (Extended Abstract) . In 29th Annual Symposium on Foundations of Computer Science , White Plains, New York, USA , 24-26 October 1988. IEEE Computer Society, 68\u201380. Jeff Kahn, Gil Kalai, and Nathan Linial. 1988. The Influence of Variables on Boolean Functions (Extended Abstract). In 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988. IEEE Computer Society, 68\u201380."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.120"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.55"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.84"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.107"},{"key":"e_1_3_2_1_30_1","volume-title":"Noisy Boolean Hidden Matching with Applications. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022","author":"Kapralov Michael","year":"2022","unstructured":"Michael Kapralov , Amulya Musipatla , Jakab Tardos , David P. Woodruff , and Samson Zhou . 2022 . Noisy Boolean Hidden Matching with Applications. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 , January 31 - February 3, 2022, Berkeley, CA, USA, Mark Braverman (Ed.) (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 91:1\u201391:19. Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, and Samson Zhou. 2022. Noisy Boolean Hidden Matching with Applications. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, Mark Braverman (Ed.) (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 91:1\u201391:19."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688093"},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016","author":"Li Yi","year":"2016","unstructured":"Yi Li and David P. Woodruff . 2016. On approximating functions of the singular values in a stream . In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 , Cambridge, MA, USA , June 18-21, 2016 , Daniel Wichs and Yishay Mansour (Eds.). ACM, 726\u2013739. Yi Li and David P. Woodruff. 2016. On approximating functions of the singular values in a stream. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, Daniel Wichs and Yishay Mansour (Eds.). ACM, 726\u2013739."},{"key":"e_1_3_2_1_33_1","volume-title":"FCT 1979, Proceedings of the Conference on Algebraic, Arthmetic, and Categorial Methods in Computation Theory, Berlin\/Wendisch-Rietz","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1979","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1979 . On determinants, matchings, and random algorithms. In Fundamentals of Computation Theory , FCT 1979, Proceedings of the Conference on Algebraic, Arthmetic, and Categorial Methods in Computation Theory, Berlin\/Wendisch-Rietz , Germany, September 17-21, 1979, Lothar Budach (Ed.). Akademie-Verlag, Berlin, 565\u2013574. L\u00e1szl\u00f3 Lov\u00e1sz. 1979. On determinants, matchings, and random algorithms. In Fundamentals of Computation Theory, FCT 1979, Proceedings of the Conference on Algebraic, Arthmetic, and Categorial Methods in Computation Theory, Berlin\/Wendisch-Rietz, Germany, September 17-21, 1979, Lothar Budach (Ed.). Akademie-Verlag, Berlin, 565\u2013574."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_2_1_35_1","volume-title":"APPROX\/RANDOM 2016","volume":"12","author":"McGregor Andrew","year":"2016","unstructured":"Andrew McGregor and Sofya Vorotnikova . 2016 . Planar Matching in Streams Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2016 , September 7-9, 2016, Paris, France, Klaus Jansen, Claire Mathieu, Jos\u00e9 D. P. Rolim, and Chris Umans (Eds.) (LIPIcs , Vol. 60). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1\u201317: 12 . Andrew McGregor and Sofya Vorotnikova. 2016. Planar Matching in Streams Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2016, September 7-9, 2016, Paris, France, Klaus Jansen, Claire Mathieu, Jos\u00e9 D. P. Rolim, and Chris Umans (Eds.) (LIPIcs, Vol. 60). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1\u201317:12."},{"key":"e_1_3_2_1_36_1","volume-title":"Streaming Algorithm for Matchings in Low Arboricity Graphs. In 1st Symposium on Simplicity in Algorithms, SOSA 2018","volume":"4","author":"McGregor Andrew","year":"2018","unstructured":"Andrew McGregor and Sofya Vorotnikova . 2018 . A Simple, Space-Efficient , Streaming Algorithm for Matchings in Low Arboricity Graphs. In 1st Symposium on Simplicity in Algorithms, SOSA 2018 , January 7-10, 2018, New Orleans, LA, USA, Raimund Seidel (Ed.) (OASIcs , Vol. 61). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 14:1\u201314: 4 . Andrew McGregor and Sofya Vorotnikova. 2018. A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs. In 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA, Raimund Seidel (Ed.) (OASIcs, Vol. 61). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 14:1\u201314:4."},{"key":"e_1_3_2_1_37_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017","volume":"14","author":"Monemizadeh Morteza","year":"2017","unstructured":"Morteza Monemizadeh , S. Muthukrishnan , Pan Peng , and Christian Sohler . 2017 . Testable Bounded Degree Graph Properties Are Random Order Streamable. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 , July 10-14, 2017, Warsaw, Poland, Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.) (LIPIcs , Vol. 80). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 131:1\u2013131: 14 . Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler. 2017. Testable Bounded Degree Graph Properties Are Random Order Streamable. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.) (LIPIcs, Vol. 80). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 131:1\u2013131:14."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019604"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.157"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch156"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-22.2.107"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133038"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.gs.2008.001"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585192","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585192","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585192","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:01Z","timestamp":1750178821000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585192"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":45,"alternative-id":["10.1145\/3564246.3585192","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585192","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}