{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T06:16:35Z","timestamp":1725776195722},"publisher-location":"New York, NY, USA","reference-count":96,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CCF-2047061"]},{"name":"Engineering and Physical Sciences Research Council","award":["EP\\\/T517872\\\/1, EP\\\/V010611\\\/1"]},{"name":"Alfred P. Sloan Foundation","award":[""]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649763","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"847-858","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"http:\/\/orcid.org\/0009-0006-8914-5995","authenticated-orcid":false,"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada \/ Rutgers University, New Brunswick, USA"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-1802-4011","authenticated-orcid":false,"given":"Christian","family":"Konrad","sequence":"additional","affiliation":[{"name":"University of Bristol, Bristol, United Kingdom"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-5946-4702","authenticated-orcid":false,"given":"Kheeran K.","family":"Naidu","sequence":"additional","affiliation":[{"name":"University of Bristol, Bristol, United Kingdom"}]},{"ORCID":"http:\/\/orcid.org\/0009-0003-0511-2124","authenticated-orcid":false,"given":"Janani","family":"Sundaresan","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897555"},{"volume-title":"Proceedings of the 32nd International Conference on Machine Learning, ICML 2015","year":"2015","author":"Ahn Kook Jin","key":"e_1_3_2_1_2_1","unstructured":"Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. 2015. Correlation Clustering in Data Streams. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015. 2237\u20132246."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154855"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095156"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060692"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Noga Alon Yossi Matias and Mario Szegedy. 1996. The space complexity of approximating the frequency moments. In STOC. 20\u201329.","DOI":"10.1145\/237814.237823"},{"volume-title":"Welfare Maximization with Limited Interaction. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015","year":"2015","author":"Alon Noga","key":"e_1_3_2_1_7_1","unstructured":"Noga Alon, Noam Nisan, Ran Raz, and Omri Weinstein. 2015. Welfare Maximization with Limited Interaction. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. 1499\u20131512."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.89"},{"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.1145\/3623800.3623808"},{"volume-title":"abs\/2307.02968. To appear in SOSA 2024","year":"2023","author":"Assadi Sepehr","key":"e_1_3_2_1_11_1","unstructured":"Sepehr Assadi. 2023. A Simple (1-)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching. CoRR, abs\/2307.02968. To appear in SOSA 2024 (2023)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316361"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.48"},{"volume-title":"35th International Symposium on Distributed Computing, DISC","year":"2021","author":"Assadi Sepehr","key":"e_1_3_2_1_14_1","unstructured":"Sepehr Assadi and Aditi Dudeja. 2021. Ruling Sets in Random Order and Adversarial Streams. In 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), Seth Gilbert (Ed.) (LIPIcs, Vol. 209). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 6:1\u20136:18."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.29"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039799"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884528"},{"volume-title":"ACM Symposium on Principles of Distributed Computing","year":"2020","author":"Assadi Sepehr","key":"e_1_3_2_1_18_1","unstructured":"Sepehr Assadi, Gillat Kol, and Rotem Oshman. 2020. Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets. In PODC \u201920: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, Yuval Emek and Christian Cachin (Eds.). ACM, 79\u201388."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00115"},{"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","year":"2021","author":"Assadi Sepehr","key":"e_1_3_2_1_20_1","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."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188922"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.116"},{"volume-title":"Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020","year":"2020","author":"Assadi Sepehr","key":"e_1_3_2_1_23_1","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."},{"key":"e_1_3_2_1_24_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","volume":"17","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi and Shay Solomon. 2019. When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.) (LIPIcs, Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1\u201317:17."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00058"},{"volume-title":"13th Innovations in Theoretical Computer Science Conference, ITCS 2022","year":"2022","author":"Assadi Sepehr","key":"e_1_3_2_1_26_1","unstructured":"Sepehr Assadi and Chen Wang. 2022. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. 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, 10:1\u201310:20."},{"volume-title":"Fully Dynamic Matching: (2-\u221a 2)-Approximation in Polylog Update Time. CoRR, abs\/2307.08772. To appear in SODA","year":"2024","author":"Azarmehr Amir","key":"e_1_3_2_1_27_1","unstructured":"Amir Azarmehr, Soheil Behnezhad, and Mohammad Roghani. 2023. Fully Dynamic Matching: (2-\u221a 2)-Approximation in Polylog Update Time. CoRR, abs\/2307.08772. To appear in SODA 2024. (2023)."},{"volume-title":"Lower Bounds for Maximal Matchings and Maximal Independent Sets. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","year":"2019","author":"Balliu Alkida","key":"e_1_3_2_1_28_1","unstructured":"Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mika\u00ebl Rabie, and Jukka Suomela. 2019. Lower Bounds for Maximal Matchings and Maximal Independent Sets. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, David Zuckerman (Ed.). IEEE Computer Society, 481\u2013497."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806701"},{"volume-title":"The Locality of Distributed Symmetry Breaking. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012","year":"2012","author":"Barenboim Leonid","key":"e_1_3_2_1_30_1","unstructured":"Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. 2012. The Locality of Distributed Symmetry Breaking. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012. IEEE Computer Society, 321\u2013330."},{"volume-title":"Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021","year":"2021","author":"Behnezhad Soheil","key":"e_1_3_2_1_31_1","unstructured":"Soheil Behnezhad. 2021. Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. IEEE, 873\u2013884."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331609"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00074"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch33"},{"key":"e_1_3_2_1_35_1","volume-title":"Streaming and Massively Parallel Algorithms for Edge Coloring. In 27th Annual European Symposium on Algorithms, ESA 2019","volume":"14","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. 2019. Streaming and Massively Parallel Algorithms for Edge Coloring. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich\/Garching, Germany, Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.) (LIPIcs, Vol. 144). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315:14."},{"volume-title":"Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","year":"2019","author":"Behnezhad Soheil","key":"e_1_3_2_1_36_1","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, David Zuckerman (Ed.). IEEE Computer Society, 382\u2013405."},{"volume-title":"Streaming Edge Coloring with Asymptotically Optimal Colors. CoRR, abs\/2305.01714","year":"2023","author":"Behnezhad Soheil","key":"e_1_3_2_1_37_1","unstructured":"Soheil Behnezhad and Mohammad Saneian. 2023. Streaming Edge Coloring with Asymptotically Optimal Colors. CoRR, abs\/2305.01714 (2023)."},{"volume-title":"Pemmaraju","year":"2012","author":"Berns Andrew","key":"e_1_3_2_1_38_1","unstructured":"Andrew Berns, James Hegeman, and Sriram V. Pemmaraju. 2012. Super-Fast Distributed Algorithms for Metric Facility Location. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer (Eds.) (Lecture Notes in Computer Science, Vol. 7392). Springer, 428\u2013439."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00079"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_42"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.101"},{"volume-title":"Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem. CoRR, abs\/2306.00432","year":"2023","author":"Cambus M\u00e9lanie","key":"e_1_3_2_1_43_1","unstructured":"M\u00e9lanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. 2023. Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem. CoRR, abs\/2306.00432 (2023)."},{"volume-title":"Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001","year":"2001","author":"Chakrabarti Amit","key":"e_1_3_2_1_44_1","unstructured":"Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Chi-Chih Yao. 2001. Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. IEEE Computer Society, 270\u2013278."},{"volume-title":"Streaming Edge Coloring with Subquadratic Palette Size. CoRR, abs\/2305.07090","year":"2023","author":"Chechik Shiri","key":"e_1_3_2_1_45_1","unstructured":"Shiri Chechik, Doron Mukhtar, and Tianyi Zhang. 2023. Streaming Edge Coloring with Subquadratic Palette Size. CoRR, abs\/2305.07090 (2023)."},{"volume-title":"Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","year":"2019","author":"Chechik Shiri","key":"e_1_3_2_1_46_1","unstructured":"Shiri Chechik and Tianyi Zhang. 2019. Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, David Zuckerman (Ed.). IEEE Computer Society, 370\u2013381."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451038"},{"volume-title":"48th International Colloquium on Automata, Languages, and Programming, ICALP","year":"2021","author":"Chen Lijie","key":"e_1_3_2_1_48_1","unstructured":"Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. 2021. Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.) (LIPIcs, Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 52:1\u201352:19."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623743"},{"key":"e_1_3_2_1_50_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning, ICML 2021","volume":"2078","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub Tarnawski. 2021. Correlation Clustering in Constant Many Parallel Rounds. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Marina Meila and Tong Zhang (Eds.) (Proceedings of Machine Learning Research, Vol. 139). PMLR, 2069\u20132078."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/050630696"},{"volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","year":"2019","author":"Cormode Graham","key":"e_1_3_2_1_52_1","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."},{"volume-title":"Thomas","year":"2006","author":"Cover Thomas M.","key":"e_1_3_2_1_53_1","unstructured":"Thomas M. Cover and Joy A. Thomas. 2006. Elements of information theory (2. ed.). Wiley. isbn:978-0-471-24195-9"},{"volume-title":"Finding structure in data streams: correlations, independent sets, and matchings. Ph. D. Dissertation","author":"Dark Jacques","key":"e_1_3_2_1_54_1","unstructured":"Jacques Dark. 2020. Finding structure in data streams: correlations, independent sets, and matchings. Ph. D. Dissertation. University of Warwick."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.140"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.142"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"volume-title":"Local Computation of Maximal Independent Set. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022","year":"2022","author":"Ghaffari Mohsen","key":"e_1_3_2_1_60_1","unstructured":"Mohsen Ghaffari. 2022. Local Computation of Maximal Independent Set. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022. IEEE, 438\u2013449."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585243"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310534"},{"volume-title":"Low-Memory Algorithms for Online and W-Streaming Edge Coloring. CoRR, abs\/2304.12285","year":"2023","author":"Ghosh Prantar","key":"e_1_3_2_1_64_1","unstructured":"Prantar Ghosh and Manuel Stoeckl. 2023. Low-Memory Algorithms for Online and W-Streaming Edge Coloring. CoRR, abs\/2304.12285 (2023)."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.41"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0138-7"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591077"},{"volume-title":"The Communication Complexity of Correlation. In 22nd Annual IEEE Conference on Computational Complexity (CCC 2007)","year":"2007","author":"Harsha Prahladh","key":"e_1_3_2_1_68_1","unstructured":"Prahladh Harsha, Rahul Jain, David A. McAllester, and Jaikumar Radhakrishnan. 2007. The Communication Complexity of Correlation. In 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA. IEEE Computer Society, 10\u201323."},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644216"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1306154"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.121"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.112"},{"volume-title":"MIS in the Congested Clique Model in O(log log \u0394 ) Rounds. CoRR, abs\/1802.07647","year":"2018","author":"Konrad Christian","key":"e_1_3_2_1_73_1","unstructured":"Christian Konrad. 2018. MIS in the Congested Clique Model in O(log log \u0394 ) Rounds. CoRR, abs\/1802.07647 (2018)."},{"key":"e_1_3_2_1_74_1","volume-title":"43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018","volume":"16","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, Igor Potapov, Paul G. Spirakis, and James Worrell (Eds.) (LIPIcs, Vol. 117). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 74:1\u201374:16."},{"volume":"18","volume-title":"APPROX\/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), Mary Wootters and Laura Sanit\u00e0 (Eds.) (LIPIcs","author":"Konrad Christian","key":"e_1_3_2_1_75_1","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), Mary Wootters and Laura Sanit\u00e0 (Eds.) (LIPIcs, Vol. 207). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1\u201319:18."},{"volume-title":"Naidu","year":"2024","author":"Konrad Christian","key":"e_1_3_2_1_76_1","unstructured":"Christian Konrad and Kheeran K. Naidu. 2024. An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024. SIAM."},{"key":"e_1_3_2_1_77_1","volume-title":"The Complexity of Symmetry Breaking in Massive Graphs. In 33rd International Symposium on Distributed Computing, DISC 2019","volume":"18","author":"Konrad Christian","year":"2019","unstructured":"Christian Konrad, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. 2019. The Complexity of Symmetry Breaking in Massive Graphs. In 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, Jukka Suomela (Ed.) (LIPIcs, Vol. 146). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 26:1\u201326:18."},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486168"},{"volume-title":"Communication complexity","author":"Kushilevitz Eyal","key":"e_1_3_2_1_80_1","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997. Communication complexity. Cambridge University Press."},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.131"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22146"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225093"},{"volume-title":"49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008","year":"2008","author":"Huy","key":"e_1_3_2_1_86_1","unstructured":"Huy N. Nguyen and Krzysztof Onak. 2008. Constant-Time Approximation Algorithms via Local Improvements. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA. IEEE Computer Society, 327\u2013336."},{"key":"e_1_3_2_1_87_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","volume":"14","author":"Onak Krzysztof","year":"2018","unstructured":"Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. 2018. Fully Dynamic MIS in Uniformly Sparse Graphs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, Ioannis Chatzigiannakis, Christos Kaklamanis, D\u00e1niel Marx, and Donald Sannella (Eds.) (LIPIcs, Vol. 107). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 92:1\u201392:14."},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108671644"},{"volume-title":"Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach\/Pacific Grove, CA, USA","year":"2016","author":"Roughgarden Tim","key":"e_1_3_2_1_89_1","unstructured":"Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. 2016. Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation). In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach\/Pacific Grove, CA, USA, July 11-13, 2016, Christian Scheideler and Seth Gilbert (Eds.). ACM, 1\u201312."},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"volume-title":"Innovations in Computer Science - ICS","year":"2011","author":"Rubinfeld Ronitt","key":"e_1_3_2_1_91_1","unstructured":"Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. 2011. Fast Local Computation Algorithms. In Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, Bernard Chazelle (Ed.). Tsinghua University Press, 223\u2013238."},{"key":"e_1_3_2_1_92_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_93_1","article-title":"Using Round Elimination to Understand Locality","volume":"79","author":"Suomela Jukka","year":"2020","unstructured":"Jukka Suomela. 2020. Using Round Elimination to Understand Locality. SIGACT News: Distributed Computing Column 79, 51, 3 (2020), 62.","journal-title":"SIGACT News: Distributed Computing Column"},{"key":"e_1_3_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/2789149.2789161"},{"volume-title":"Simpler and Higher Lower Bounds for Shortcut Sets. CoRR, abs\/2310.12051","year":"2023","author":"Williams Virginia Vassilevska","key":"e_1_3_2_1_95_1","unstructured":"Virginia Vassilevska Williams, Yinzhan Xu, and Zixuan Xu. 2023. Simpler and Higher Lower Bounds for Shortcut Sets. CoRR, abs\/2310.12051 (2023)."},{"key":"e_1_3_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536447"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T21:22:24Z","timestamp":1718918544000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":96,"alternative-id":["10.1145\/3618260.3649763","10.1145\/3618260"],"URL":"http:\/\/dx.doi.org\/10.1145\/3618260.3649763","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}