{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,23]],"date-time":"2024-07-23T13:26:33Z","timestamp":1721741193799},"publisher-location":"New York, NY, USA","reference-count":83,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,2]],"date-time":"2024-06-02T00:00:00Z","timestamp":1717286400000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2047061, CCF-1934876, CCF-2008305"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585110","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["On Regularity Lemma and Barriers in Streaming and Dynamic Matching"],"prefix":"10.1145","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"Rutgers University, USA"}]},{"given":"Soheil","family":"Behnezhad","sequence":"additional","affiliation":[{"name":"Northeastern University, USA"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}]},{"given":"Huan","family":"Li","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, Luca Aceto, Monika Henzinger, and Jir\u00ed Sgall (Eds.) (Lecture Notes in Computer Science","volume":"538","author":"Ahn Kook Jin","year":"2011","unstructured":"Kook Jin Ahn and Sudipto Guha . 2011 . Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, Luca Aceto, Monika Henzinger, and Jir\u00ed Sgall (Eds.) (Lecture Notes in Computer Science , Vol. 6756). Springer, 526\u2013 538 . Kook Jin Ahn and Sudipto Guha. 2011. Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, Luca Aceto, Monika Henzinger, and Jir\u00ed Sgall (Eds.) (Lecture Notes in Computer Science, Vol. 6756). Springer, 526\u2013538."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154855"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"e_1_3_2_1_5_1","volume-title":"33rd Annual Symposium on Foundations of Computer Science","author":"Alon Noga","year":"1992","unstructured":"Noga Alon , Richard A. Duke , Hanno Lefmann , Vojtech R\u00f6dl , and Raphael Yuster . 1992 . The Algorithmic Aspects of the Regularity Lemma (Extended Abstract) . In 33rd Annual Symposium on Foundations of Computer Science , Pittsburgh, Pennsylvania, USA , 24-27 October 1992. IEEE Computer Society, 473\u2013481. Noga Alon, Richard A. Duke, Hanno Lefmann, Vojtech R\u00f6dl, and Raphael Yuster. 1992. The Algorithmic Aspects of the Regularity Lemma (Extended Abstract). In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992. IEEE Computer Society, 473\u2013481."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214074"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007759"},{"key":"e_1_3_2_1_8_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","author":"Arar Moab","year":"2018","unstructured":"Moab Arar , Shiri Chechik , Sarel Cohen , Cliff Stein , and David Wajc . 2018 . Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , July 9-13, 2018, Prague, Czech Republic. 7:1\u20137:16. Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc. 2018. Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic. 7:1\u20137:16."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.32"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.98"},{"key":"e_1_3_2_1_11_1","volume-title":"48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference) (LIPIcs","volume":"13","author":"Assadi Sepehr","year":"2021","unstructured":"Sepehr Assadi and Soheil Behnezhad . 2021 . Beating Two-Thirds For Random-Order Streaming Matching. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference) (LIPIcs , Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1\u201319: 13 . Sepehr Assadi and Soheil Behnezhad. 2021. Beating Two-Thirds For Random-Order Streaming Matching. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference) (LIPIcs, Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1\u201319:13."},{"key":"e_1_3_2_1_12_1","volume-title":"2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi and Aaron Bernstein . 2019 . Towards a Unified Theory of Sparsification for Matching Problems . In 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019 , January 8-9, 2019 - San Diego, CA, USA. 11:1\u201311:20. Sepehr Assadi and Aaron Bernstein. 2019. Towards a Unified Theory of Sparsification for Matching Problems. In 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, January 8-9, 2019 - San Diego, CA, USA. 11:1\u201311:20."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.29"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085146"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355903"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884528"},{"key":"e_1_3_2_1_17_1","volume-title":"An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference","author":"Assadi Sepehr","year":"2021","unstructured":"Sepehr Assadi , S. Cliff Liu , and Robert E. Tarjan . 2021 . An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference , January 11-12, 2021 , Hung Viet Le and Valerie King (Eds.). SIAM, 165\u2013171. Sepehr Assadi, S. Cliff Liu, and Robert E. Tarjan. 2021. An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, Hung Viet Le and Valerie King (Eds.). SIAM, 165\u2013171."},{"key":"e_1_3_2_1_18_1","volume-title":"Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020","author":"Assadi Sepehr","year":"2020","unstructured":"Sepehr Assadi and Ran Raz . 2020 . Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 , Durham, NC, USA , November 16-19, 2020, Sandy Irani (Ed.). IEEE, 342\u2013353. Sepehr Assadi and Ran Raz. 2020. Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, Sandy Irani (Ed.). IEEE, 342\u2013353."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.89"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1106158"},{"key":"e_1_3_2_1_21_1","volume-title":"To appear in SODA","author":"Behnezhad Soheil","year":"2023","unstructured":"Soheil Behnezhad . 2022. To appear in SODA 2023 . Dynamic Algorithms for Maximum Matching Size. CoRR, abs\/2207.07607 (2022. To appear in SODA 2023). Soheil Behnezhad. 2022. To appear in SODA 2023. Dynamic Algorithms for Maximum Matching Size. CoRR, abs\/2207.07607 (2022. To appear in SODA 2023)."},{"key":"e_1_3_2_1_22_1","volume-title":"Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad , Mahsa Derakhshan , MohammadTaghi Hajiaghayi , Cliff Stein , and Madhu Sudan . 2019 . Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 , Baltimore, Maryland, USA , November 9-12, 2019. IEEE Computer Society, 382\u2013405. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. 2019. Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019. IEEE Computer Society, 382\u2013405."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.140"},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020","author":"Behnezhad Soheil","year":"2020","unstructured":"Soheil Behnezhad , Jakub Lacki , and Vahab S. Mirrokni . 2020. Fully Dynamic Matching: Beating 2-Approximation in \u0394 ^\u220a Update Time . In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 , Salt Lake City, UT, USA , January 5-8, 2020 . SIAM, 2492\u20132508. Soheil Behnezhad, Jakub Lacki, and Vahab S. Mirrokni. 2020. Fully Dynamic Matching: Beating 2-Approximation in \u0394 ^\u220a Update Time. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020. SIAM, 2492\u20132508."},{"key":"e_1_3_2_1_25_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 12:1\u201312:13","author":"Bernstein Aaron","year":"2020","unstructured":"Aaron Bernstein . 2020 . Improved Bounds for Matching in Random-Order Streams. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 12:1\u201312:13 . Aaron Bernstein. 2020. Improved Bounds for Matching in Random-Order Streams. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 12:1\u201312:13."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451113"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.115"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_14"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/140998925"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039716"},{"key":"e_1_3_2_1_33_1","volume-title":"48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference). 27:1\u201327:14","author":"Bhattacharya Sayan","year":"2021","unstructured":"Sayan Bhattacharya and Peter Kiss . 2021 . Deterministic Rounding of Dynamic Fractional Matchings. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference). 27:1\u201327:14 . Sayan Bhattacharya and Peter Kiss. 2021. Deterministic Rounding of Dynamic Fractional Matchings. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference). 27:1\u201327:14."},{"key":"e_1_3_2_1_34_1","volume-title":"To appear in SODA","author":"Bhattacharya Sayan","year":"2023","unstructured":"Sayan Bhattacharya , Peter Kiss , Thatchaphol Saranurak , and David Wajc . 2022. To appear in SODA 2023 . Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. CoRR, abs\/2207.07438 (2022. To appear in SODA 2023). Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, and David Wajc. 2022. To appear in SODA 2023. Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. CoRR, abs\/2207.07438 (2022. To appear in SODA 2023)."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.179355"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294165"},{"key":"e_1_3_2_1_37_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","author":"Charikar Moses","year":"2018","unstructured":"Moses Charikar and Shay Solomon . 2018 . Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , July 9-13, 2018, Prague, Czech Republic. 33:1\u201333:14. Moses Charikar and Shay Solomon. 2018. Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic. 33:1\u201333:14."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451038"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch92"},{"key":"e_1_3_2_1_40_1","volume-title":"Graph removal lemmas.. Surveys in combinatorics, 409","author":"Conlon David","year":"2013","unstructured":"David Conlon and Jacob Fox . 2013. Graph removal lemmas.. Surveys in combinatorics, 409 ( 2013 ), 1\u201349. David Conlon and Jacob Fox. 2013. Graph removal lemmas.. Surveys in combinatorics, 409 (2013), 1\u201349."},{"key":"e_1_3_2_1_41_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12","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 2019, July 9-12 , 2019, Patras, Greece. 45:1\u201345:14. Graham Cormode, Jacques Dark, and Christian Konrad. 2019. Independent Sets in Vertex-Arrival Streams. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece. 45:1\u201345:14."},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020","author":"Farhadi Alireza","year":"2020","unstructured":"Alireza Farhadi , Mohammad Taghi Hajiaghayi , Tung Mai , Anup Rao , and Ryan A. Rossi . 2020. Approximate Maximum Matching in Random Streams . In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 , Salt Lake City, UT, USA , January 5-8, 2020 . 1773\u20131785. Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mai, Anup Rao, and Ryan A. Rossi. 2020. Approximate Maximum Matching in Random Streams. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020. 1773\u20131785."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_3_2_1_44_1","volume-title":"Maximum Matching sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model. CoRR, abs\/2109.05946. To appear in APPROX","author":"Feldman Moran","year":"2022","unstructured":"Moran Feldman and Ariel Szarf . 2021. Maximum Matching sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model. CoRR, abs\/2109.05946. To appear in APPROX 2022 . (2021). Moran Feldman and Ariel Szarf. 2021. Maximum Matching sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model. CoRR, abs\/2109.05946. To appear in APPROX 2022. (2021)."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520039"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2011.174.1.17"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12005"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12005"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.41"},{"key":"e_1_3_2_1_51_1","volume-title":"Some unsolved problems in additive\/combinatorial number theory. preprint, 4","author":"Gowers WT","year":"2001","unstructured":"WT Gowers . 2001. Some unsolved problems in additive\/combinatorial number theory. preprint, 4 ( 2001 ). WT Gowers. 2001. Some unsolved problems in additive\/combinatorial number theory. preprint, 4 (2001)."},{"key":"e_1_3_2_1_52_1","volume-title":"Density-Sensitive and with Worst-Case Time Bounds. In 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference","author":"Grandoni Fabrizio","year":"2022","unstructured":"Fabrizio Grandoni , Chris Schwiegelshohn , Shay Solomon , and Amitai Uzrad . 2022 . Maintaining an EDCS in General Graphs: Simpler , Density-Sensitive and with Worst-Case Time Bounds. In 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference , January 10-11, 2022. SIAM, 12\u201323. Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, and Amitai Uzrad. 2022. Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds. In 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022. SIAM, 12\u201323."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Philip Hall. 1987. On representatives of subsets. Classic Papers in Combinatorics 58\u201362. \t\t\t\t Philip Hall. 1987. On representatives of subsets. Classic Papers in Combinatorics 58\u201362.","DOI":"10.1007\/978-0-8176-4842-8_4"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10068"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_1_57_1","volume-title":"19th International Workshop, WG \u201993, Utrecht, The Netherlands, June 16-18, 1993, Proceedings (Lecture Notes in Computer Science","volume":"111","author":"Ivkovic Zoran","unstructured":"Zoran Ivkovic and Errol L. Lloyd . 1993. Fully Dynamic Maintenance of Vertex Cover. In Graph-Theoretic Concepts in Computer Science , 19th International Workshop, WG \u201993, Utrecht, The Netherlands, June 16-18, 1993, Proceedings (Lecture Notes in Computer Science , Vol. 790). Springer, 99\u2013 111 . Zoran Ivkovic and Errol L. Lloyd. 1993. Fully Dynamic Maintenance of Vertex Cover. In Graph-Theoretic Concepts in Computer Science, 19th International Workshop, WG \u201993, Utrecht, The Netherlands, June 16-18, 1993, Proceedings (Lecture Notes in Computer Science, Vol. 790). Springer, 99\u2013111."},{"key":"e_1_3_2_1_58_1","volume-title":"APPROX\/RANDOM 2017","volume":"21","author":"Kale Sagar","year":"2017","unstructured":"Sagar Kale and Sumedh Tirodkar . 2017 . Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2017 , August 16-18, 2017, Berkeley, CA, USA (LIPIcs , Vol. 81). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315: 21 . Sagar Kale and Sumedh Tirodkar. 2017. Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA (LIPIcs, Vol. 81). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315:21."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.121"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.112"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451061"},{"key":"e_1_3_2_1_62_1","volume-title":"Optimal Quantile Approximation in Streams. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016","author":"Karnin Zohar S.","year":"2016","unstructured":"Zohar S. Karnin , Kevin J. Lang , and Edo Liberty . 2016 . Optimal Quantile Approximation in Streams. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016 , 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, Irit Dinur (Ed.). IEEE Computer Society, 71\u201378. Zohar S. Karnin, Kevin J. Lang, and Edo Liberty. 2016. Optimal Quantile Approximation in Streams. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, Irit Dinur (Ed.). IEEE Computer Society, 71\u201378."},{"key":"e_1_3_2_1_63_1","volume-title":"Deterministic Dynamic Matching in Worst-Case Update Time. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022","volume":"21","author":"Kiss Peter","year":"2022","unstructured":"Peter Kiss . 2022 . Deterministic Dynamic Matching in Worst-Case Update Time. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 , January 31 - February 3, 2022, Berkeley, CA, USA (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 94:1\u201394: 21 . Peter Kiss. 2022. Deterministic Dynamic Matching in Worst-Case Update Time. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 94:1\u201394:21."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456961"},{"key":"e_1_3_2_1_65_1","volume-title":"Proceedings. 840\u2013852","author":"Konrad Christian","year":"2015","unstructured":"Christian Konrad . 2015 . Maximum Matching in Turnstile Streams. In Algorithms - ESA 2015 - 23rd Annual European Symposium, September 14-16, 2015 , Proceedings. 840\u2013852 . Christian Konrad. 2015. Maximum Matching in Turnstile Streams. In Algorithms - ESA 2015 - 23rd Annual European Symposium, September 14-16, 2015, Proceedings. 840\u2013852."},{"key":"e_1_3_2_1_66_1","volume-title":"43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018","author":"Konrad Christian","year":"2018","unstructured":"Christian Konrad . 2018 . A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms . In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 , August 27-31, 2018, Liverpool, UK. 74:1\u201374:16. Christian Konrad. 2018. A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK. 74:1\u201374:16."},{"key":"e_1_3_2_1_67_1","volume-title":"APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings (Lecture Notes in Computer Science","volume":"242","author":"Konrad Christian","year":"2012","unstructured":"Christian Konrad , Fr\u00e9d\u00e9ric Magniez , and Claire Mathieu . 2012 . Maximum Matching in Semi-streaming with Few Passes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop , APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings (Lecture Notes in Computer Science , Vol. 7408). Springer, 231\u2013 242 . Christian Konrad, Fr\u00e9d\u00e9ric Magniez, and Claire Mathieu. 2012. Maximum Matching in Semi-streaming with Few Passes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings (Lecture Notes in Computer Science, Vol. 7408). Springer, 231\u2013242."},{"key":"e_1_3_2_1_68_1","volume-title":"APPROX\/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference) (LIPIcs","volume":"18","author":"Konrad Christian","unstructured":"Christian Konrad and Kheeran K. Naidu . 2021. On Two-Pass Streaming Algorithms for Maximum Bipartite Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference) (LIPIcs , Vol. 207). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1\u201319: 18 . Christian Konrad and Kheeran K. Naidu. 2021. On Two-Pass Streaming Algorithms for Maximum Bipartite Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference) (LIPIcs, Vol. 207). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1\u201319:18."},{"key":"e_1_3_2_1_69_1","volume-title":"Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets. In SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data","author":"Manku Gurmeet Singh","year":"1999","unstructured":"Gurmeet Singh Manku , Sridhar Rajagopalan , and Bruce G. Lindsay . 1999 . Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets. In SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data , June 1-3, 1999 , Philadelphia, Pennsylvania, USA, Alex Delis, Christos Faloutsos, and Shahram Ghandeharizadeh (Eds.). ACM Press, 251\u2013262. Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. 1999. Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets. In SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1-3, 1999, Philadelphia, Pennsylvania, USA, Alex Delis, Christos Faloutsos, and Shahram Ghandeharizadeh (Eds.). ACM Press, 251\u2013262."},{"key":"e_1_3_2_1_70_1","unstructured":"Andrew McGregor. 2005. Finding Graph Matchings in Data Streams. In Approximation Randomization and Combinatorial Optimization Algorithms and Techniques 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation RANDOM 2005 Berkeley CA USA August 22-24 2005 Proceedings Chandra Chekuri Klaus Jansen Jos\u00e9 D. P. Rolim and Luca Trevisan (Eds.) (Lecture Notes in Computer Science Vol. 3624). Springer 170\u2013181. \t\t\t\t Andrew McGregor. 2005. Finding Graph Matchings in Data Streams. In Approximation Randomization and Combinatorial Optimization Algorithms and Techniques 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation RANDOM 2005 Berkeley CA USA August 22-24 2005 Proceedings Chandra Chekuri Klaus Jansen Jos\u00e9 D. P. Rolim and Luca Trevisan (Eds.) (Lecture Notes in Computer Science Vol. 3624). Springer 170\u2013181."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488703"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"e_1_3_2_1_75_1","volume-title":"30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings (Lecture Notes in Computer Science","volume":"368","author":"Raman Rajeev","unstructured":"Rajeev Raman and S. Srinivasa Rao . 2003. Succinct Dynamic Dictionaries and Trees. In Automata, Languages and Programming , 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings (Lecture Notes in Computer Science , Vol. 2719). Springer, 357\u2013 368 . Rajeev Raman and S. Srinivasa Rao. 2003. Succinct Dynamic Dictionaries and Trees. In Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings (Lecture Notes in Computer Science, Vol. 2719). Springer, 357\u2013368."},{"key":"e_1_3_2_1_76_1","volume-title":"Beating the Folklore Algorithm for Dynamic Matching. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022","volume":"23","author":"Roghani Mohammad","year":"2022","unstructured":"Mohammad Roghani , Amin Saberi , and David Wajc . 2022 . Beating the Folklore Algorithm for Dynamic Matching. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 , January 31 - February 3, 2022, Berkeley, CA, USA (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 111:1\u2013111: 23 . Mohammad Roghani, Amin Saberi, and David Wajc. 2022. Beating the Folklore Algorithm for Dynamic Matching. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 111:1\u2013111:23."},{"key":"e_1_3_2_1_77_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 \u2013 945 . 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_78_1","volume-title":"Fully Dynamic Maximal Matching in Constant Update Time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016","author":"Solomon Shay","year":"2016","unstructured":"Shay Solomon . 2016 . Fully Dynamic Maximal Matching in Constant Update Time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016 , 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. IEEE Computer Society, 325\u2013334. Shay Solomon. 2016. Fully Dynamic Maximal Matching in Constant Update Time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. IEEE Computer Society, 325\u2013334."},{"key":"e_1_3_2_1_79_1","volume-title":"Fully Dynamic Maximal Matching in Constant Update Time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016","author":"Solomon Shay","year":"2016","unstructured":"Shay Solomon . 2016 . Fully Dynamic Maximal Matching in Constant Update Time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016 , 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. IEEE Computer Society, 325\u2013334. Shay Solomon. 2016. Fully Dynamic Maximal Matching in Constant Update Time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. IEEE Computer Society, 325\u2013334."},{"key":"e_1_3_2_1_80_1","unstructured":"Endre Szemer\u00e9di. 1975. Regular partitions of graphs. Stanford Univ Calif Dept of Computer Science. \t\t\t\t Endre Szemer\u00e9di. 1975. Regular partitions of graphs. Stanford Univ Calif Dept of Computer Science."},{"key":"e_1_3_2_1_81_1","volume-title":"Additive combinatorics. 105","author":"Tao Terence","unstructured":"Terence Tao and Van H Vu. 2006. Additive combinatorics. 105 , Cambridge University Press . Terence Tao and Van H Vu. 2006. Additive combinatorics. 105, Cambridge University Press."},{"key":"e_1_3_2_1_82_1","volume-title":"Matching Theory Under Uncertainty. Ph. D. Dissertation","author":"Wajc David","unstructured":"David Wajc . 2020. Matching Theory Under Uncertainty. Ph. D. Dissertation . Carnegie Mellon University . David Wajc. 2020. Matching Theory Under Uncertainty. Ph. D. Dissertation. Carnegie Mellon University."},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384258"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585110","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T15:21:57Z","timestamp":1686583317000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":83,"alternative-id":["10.1145\/3564246.3585110","10.1145\/3564246"],"URL":"http:\/\/dx.doi.org\/10.1145\/3564246.3585110","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"}}]}}