{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:47:08Z","timestamp":1750308428723,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520016","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"261-274","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Deterministic graph coloring in the streaming model"],"prefix":"10.1145","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"Rutgers University, USA"}]},{"given":"Andrew","family":"Chen","sequence":"additional","affiliation":[{"name":"Cornell University, USA"}]},{"given":"Glenn","family":"Sun","sequence":"additional","affiliation":[{"name":"University of California at Los Angeles, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Higher Lower Bounds. CoRR, abs\/1901.01630","author":"Abboud Amir","year":"2019","unstructured":"Amir Abboud , Keren Censor-Hillel , Seri Khoury , and Ami Paz . 2019. Smaller Cuts , Higher Lower Bounds. CoRR, abs\/1901.01630 ( 2019 ). Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. 2019. Smaller Cuts, Higher Lower Bounds. CoRR, abs\/1901.01630 (2019)."},{"key":"e_1_3_2_1_2_1","volume-title":"APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference, Jaroslaw Byrka and Raghu Meka (Eds.) (LIPIcs","volume":"22","author":"Alon Noga","year":"2020","unstructured":"Noga Alon and Sepehr Assadi . 2020 . Palette Sparsification Beyond (\u0394 + 1) Vertex Coloring. 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, 6:1\u20136: 22 . Noga Alon and Sepehr Assadi. 2020. Palette Sparsification Beyond (\u0394 + 1) Vertex Coloring. 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, 6:1\u20136:22."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.48"},{"key":"e_1_3_2_1_4_1","volume-title":"35th International Symposium on Distributed Computing, DISC","author":"Assadi Sepehr","year":"2021","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 . 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_5_1","volume-title":"4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference","author":"Assadi Sepehr","year":"2021","unstructured":"Sepehr Assadi and Aditi Dudeja . 2021 . A Simple Semi-Streaming Algorithm for Global Minimum Cuts . In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference , January 11-12, 2021, Hung Viet Le and Valerie King (Eds.). SIAM, 172\u2013180. Sepehr Assadi and Aditi Dudeja. 2021. A Simple Semi-Streaming Algorithm for Global Minimum Cuts. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, Hung Viet Le and Valerie King (Eds.). SIAM, 172\u2013180."},{"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","volume-title":"STOC 2022","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi , Pankaj Kumar , and Parth Mittal . 2022 . Brooks\u2019 Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for \u0394 -Coloring. CoRR, abs\/2203.10984 . In STOC 2022 . (2022). Sepehr Assadi, Pankaj Kumar, and Parth Mittal. 2022. Brooks\u2019 Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for \u0394 -Coloring. CoRR, abs\/2203.10984. In STOC 2022. (2022)."},{"key":"e_1_3_2_1_8_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 . 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."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387658"},{"key":"e_1_3_2_1_10_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 11:1\u201311:21","author":"Bera Suman K.","year":"2020","unstructured":"Suman K. Bera , Amit Chakrabarti , and Prantar Ghosh . 2020 . Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 11:1\u201311:21 . Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. 2020. Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 11:1\u201311:21."},{"key":"e_1_3_2_1_11_1","volume-title":"Coloring in Graph Streams. CoRR, abs\/1807.07640","author":"Bera Suman Kalyan","year":"2018","unstructured":"Suman Kalyan Bera and Prantar Ghosh . 2018. Coloring in Graph Streams. CoRR, abs\/1807.07640 ( 2018 ). Suman Kalyan Bera and Prantar Ghosh. 2018. Coloring in Graph Streams. CoRR, abs\/1807.07640 (2018)."},{"key":"e_1_3_2_1_12_1","volume-title":"12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, James R. Lee (Ed.) (LIPIcs","volume":"19","author":"Bhattacharya Anup","year":"2021","unstructured":"Anup Bhattacharya , Arijit Bishnu , Gopinath Mishra , and Anannya Upasana . 2021 . Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming! . In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, James R. Lee (Ed.) (LIPIcs , Vol. 185). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315: 19 . Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, and Anannya Upasana. 2021. Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, James R. Lee (Ed.) (LIPIcs, Vol. 185). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315:19."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002168X"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00376-1"},{"key":"e_1_3_2_1_15_1","volume-title":"Adversarially Robust Coloring for Graph Streams. 215","author":"Chakrabarti Amit","year":"2022","unstructured":"Amit Chakrabarti , Prantar Ghosh , and Manuel Stoeckl . 2022. Adversarially Robust Coloring for Graph Streams. 215 ( 2022 ), 37:1\u201337:23. Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. 2022. Adversarially Robust Coloring for Graph Streams. 215 (2022), 37:1\u201337:23."},{"key":"e_1_3_2_1_16_1","volume-title":"ISCO 2018","author":"Cormode Graham","year":"2018","unstructured":"Graham Cormode , Jacques Dark , and Christian Konrad . 2018 . Approximating the Caro-Wei Bound for Independent Sets in Graph Streams. In Combinatorial Optimization - 5th International Symposium , ISCO 2018 , Marrakesh, Morocco , April 11-13, 2018, Revised Selected Papers, Jon Lee, Giovanni Rinaldi, and Ali Ridha Mahjoub (Eds.) (Lecture Notes in Computer Science, Vol. 10856). Springer, 101\u2013114. Graham Cormode, Jacques Dark, and Christian Konrad. 2018. Approximating the Caro-Wei Bound for Independent Sets in Graph Streams. In Combinatorial Optimization - 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, Revised Selected Papers, Jon Lee, Giovanni Rinaldi, and Ali Ridha Mahjoub (Eds.) (Lecture Notes in Computer Science, Vol. 10856). Springer, 101\u2013114."},{"key":"e_1_3_2_1_17_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","volume":"14","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, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.) (LIPIcs , Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 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, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.) (LIPIcs, Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 45:1\u201345:14."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405751"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3451992"},{"key":"e_1_3_2_1_20_1","volume-title":"ACM Symposium on Principles of Distributed Computing","author":"Czumaj Artur","year":"2021","unstructured":"Artur Czumaj , Peter Davies , and Merav Parter . 2021 . Improved Deterministic (\u0394 + 1) Coloring in Low-Space MPC. In PODC \u201921 : ACM Symposium on Principles of Distributed Computing , Virtual Event, Italy , July 26-30, 2021, Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen (Eds.). ACM, 469\u2013479. Artur Czumaj, Peter Davies, and Merav Parter. 2021. Improved Deterministic (\u0394 + 1) Coloring in Low-Space MPC. In PODC \u201921: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen (Eds.). ACM, 469\u2013479."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2013.6638794"},{"key":"e_1_3_2_1_22_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_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_3_2_1_25_1","volume-title":"Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. CoRR, abs\/2011.04511. To appear in FOCS 2021","author":"Ghaffari Mohsen","year":"2020","unstructured":"Mohsen Ghaffari and Fabian Kuhn . 2020. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. CoRR, abs\/2011.04511. To appear in FOCS 2021 ( 2020 ). Mohsen Ghaffari and Fabian Kuhn. 2020. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. CoRR, abs\/2011.04511. To appear in FOCS 2021 (2020)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2010.2045092"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745763"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0051-5"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_38"},{"key":"e_1_3_2_1_30_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 . 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_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_2_1_32_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","volume":"14","author":"Parter Merav","year":"2018","unstructured":"Merav Parter . 2018 . (\u0394 + 1) Coloring in the Congested Clique Model. 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, 160:1\u2013160: 14 . Merav Parter. 2018. (\u0394 + 1) Coloring in the Congested Clique Model. 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, 160:1\u2013160:14."},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"Paz Ami","year":"2017","unstructured":"Ami Paz and Gregory Schwartzman . 2017. A (2+)-Approximation for Maximum Weight Matching in the Semi-Streaming Model . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 , Barcelona, Spain, Hotel Porta Fira, January 16-19, Philip N. Klein (Ed.). SIAM , 2153\u20132161. Ami Paz and Gregory Schwartzman. 2017. A (2+)-Approximation for Maximum Weight Matching in the Semi-Streaming Model. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, Philip N. Klein (Ed.). SIAM, 2153\u20132161."},{"key":"e_1_3_2_1_34_1","volume-title":"Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). In 18th Annual Symposium on Foundations of Computer Science","author":"Chi-Chih Yao Andrew","year":"1977","unstructured":"Andrew Chi-Chih Yao . 1977 . Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). In 18th Annual Symposium on Foundations of Computer Science , Providence, Rhode Island , USA, 31 October - 1 November 1977. IEEE Computer Society, 222\u2013227. Andrew Chi-Chih Yao. 1977. Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977. IEEE Computer Society, 222\u2013227."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520016","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520016","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520016"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":34,"alternative-id":["10.1145\/3519935.3520016","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520016","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}