{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T05:11:45Z","timestamp":1742965905882,"version":"3.40.3"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030549206"},{"type":"electronic","value":"9783030549213"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-54921-3_1","type":"book-chapter","created":{"date-parts":[[2020,7,29]],"date-time":"2020-07-29T11:04:28Z","timestamp":1596020668000},"page":"3-18","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Network Decomposition and Distributed Derandomization (Invited Paper)"],"prefix":"10.1007","author":[{"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,28]]},"reference":[{"issue":"4","key":"1_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"issue":"2","key":"1_CR2","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1006\/jpdc.1996.0159","volume":"39","author":"B Awerbuch","year":"1996","unstructured":"Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Fast network decompositions and covers. J. Parallel Distrib. Comput. 39(2), 105\u2013114 (1996)","journal-title":"J. Parallel Distrib. Comput."},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proceedings of 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"1_CR4","unstructured":"Awerbuch, B., Peleg, D.: Sparse partitions. In: Proceedings of 31st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 503\u2013513 (1990)"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Balliu, A., Brandt, S., Hirvonen, J., Olivetti, D., Rabie, M., Suomela, J.: Lower bounds for maximal matchings and maximal independent sets. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS) (2019)","DOI":"10.1109\/FOCS.2019.00037"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Balliu, A., Brandt, S., Olivetti, D., Suomela, J.: How much does randomness help with locally checkable problems? In: Proceedings of the Symposium on Principles of Distributed Computing (PODC), pp. to appear, arXiv:1902.06803 (2020)","DOI":"10.1145\/3382734.3405715"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Bamberger, P., Kuhn, F., Maus, Y.: Efficient deterministic distributed coloring with small bandwidth. In: Proceedings of the Symposium on Principles of Distributed Computing (PODC), pp. to appear, arXiv:1912.02814 (2020)","DOI":"10.1145\/3382734.3404504"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. In: Proceedings of 29th Symposium on Principles of Distributed Computing (PODC), pp. 410\u2013419 (2010)","DOI":"10.1145\/1835698.1835797"},{"issue":"1","key":"1_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00520ED1V01Y201307DCT011","volume":"4","author":"L Barenboim","year":"2013","unstructured":"Barenboim, L., Elkin, M.: Distributed graph coloring: fundamentals and recent developments. Synthesis Lect. Distrib. Comput. Theory 4(1), 1\u2013177 (2013)","journal-title":"Synthesis Lect. Distrib. Comput. Theory"},{"issue":"3","key":"1_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2903137","volume":"63","author":"L Barenboim","year":"2016","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 1\u201345 (2016)","journal-title":"J. ACM"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Brandt, S., et al.: A lower bound for the distributed Lov\u00e1sz local lemma. In: Proceedings of the Symposium on Theory of Computation (STOC), pp. 479\u2013488 (2016)","DOI":"10.1145\/2897518.2897570"},{"key":"1_CR12","unstructured":"Censor-Hillel, K., Parter, M., Schwartzman, G.: Derandomizing local distributed algorithms under bandwidth restrictions. In: Proceedings of the Symposium on DIStributed Computing (DISC) (2017)"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Chang, Y.J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. In: Proceedings of 57th IEEE Symposium on Foundations of Computer Science (FOCS) (2016)","DOI":"10.1109\/FOCS.2016.72"},{"key":"1_CR14","unstructured":"Chang, Y.J., Li, W., Pettie, S.: An optimal distributed $$(\\varDelta + 1) $$-coloring algorithm? In: Proceedings of 50th ACM Symposium on Theory of Computing (STOC) (2018)"},{"issue":"3","key":"1_CR15","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1137\/19M1249527","volume":"49","author":"YJ Chang","year":"2020","unstructured":"Chang, Y.J., Li, W., Pettie, S.: Distributed ($${\\varDelta }$$+1)-coloring viaultrafast graph shattering. SIAM J. Comput. 49(3), 497\u2013539 (2020)","journal-title":"SIAM J. Comput."},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Deurer, J., Kuhn, F., Maus, Y.: Deterministic distributed dominating set approximation in the congest model. In: Proceedings of the Symposium on Principles of Distributed Computing (PODC), pp. 94\u2013103 (2019)","DOI":"10.1145\/3293611.3331626"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O.: Distributed strong diameter network decomposition. In: Proceedings of the Symposium on Principles of Distributed Computing (PODC) (2016)","DOI":"10.1145\/2933057.2933094"},{"key":"1_CR18","unstructured":"Fischer, M.: Improved Deterministic Distributed Matching via Rounding. In: Proceedings of the Symposium on DIStributed Computing (DISC), pp. 1\u201315 (2017)"},{"key":"1_CR19","unstructured":"Fischer, M.: Improved deterministic distributed matching via rounding. Distrib. Comput. 1\u201313 (2018)"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"Fischer, M., Ghaffari, M., Kuhn, F.: Deterministic distributed edge-coloring via hypergraph maximal matching. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS) (2017)","DOI":"10.1109\/FOCS.2017.25"},{"issue":"1","key":"1_CR21","first-page":"12","volume":"54","author":"C Gavoille","year":"2009","unstructured":"Gavoille, C., Klasing, R., Kosowski, A., Kuszner, \u0141., Navarra, A.: On the complexity of distributed graph coloring with local minimality constraints. Netw. Int. J. 54(1), 12\u201319 (2009)","journal-title":"Netw. Int. J."},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 270\u2013277 (2016)","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: Distributed maximal independent set using small messages. In: Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 805\u2013820 (2019)","DOI":"10.1137\/1.9781611975482.50"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Harris, D., Kuhn, F.: On derandomizing local distributed algorithms. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 662\u2013673 (2018)","DOI":"10.1109\/FOCS.2018.00069"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Hirvonen, J., Kuhn, F., Maus, Y., Suomela, J., Uitto, J.: Improved distributed degree splitting and edge coloring. In: Proceedings of the Symposium on DIStributed Computing (DISC) (2017)","DOI":"10.1145\/3212734.3212764"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F.: Derandomizing distributed algorithms with small messages: Spanners and dominating set. In: 32nd International Symposium on Distributed Computing (DISC 2018) (2018)","DOI":"10.1109\/FOCS.2018.00069"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F.: On the use of randomness in local distributed graph algorithms. In: Proceedings of the Symposium on Principles of Distributed Computing (PODC), pp. 290\u2013299 (2019)","DOI":"10.1145\/3293611.3331610"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Maus, Y.: On the complexity of local distributed graph problems. In: Proceedings of the Symposium on Theory of Computation (STOC), pp. 784\u2013797 (2017)","DOI":"10.1145\/3055399.3055471"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Maus, Y., Uitto, J.: Deterministic distributed edge-coloring with fewer colors. In: Proceedings of the Symposium on Theory of Computation (STOC), pp. 418\u2013430 (2018)","DOI":"10.1145\/3188745.3188906"},{"key":"1_CR30","unstructured":"Ghaffari, M., Portmann, J.: Improved network decompositions using small messages with applications on mis, neighborhood covers, and beyond. In: 33rd International Symposium on Distributed Computing (DISC 2019) (2019)"},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Su, H.H.: Distributed degree splitting, edge coloring, and orientations. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2505\u20132523. Society for Industrial and Applied Mathematics (2017)","DOI":"10.1137\/1.9781611974782.166"},{"issue":"3","key":"1_CR32","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1137\/0402028","volume":"2","author":"M Goldberg","year":"1989","unstructured":"Goldberg, M., Spencer, T.: Constructing a maximal independent set in parallel. SIAM J. Discrete Math. 2(3), 322\u2013328 (1989)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1_CR33","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0895480100373121","volume":"15","author":"M Ha\u0144\u0107kowiak","year":"2001","unstructured":"Ha\u0144\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. SIAM J. Discrete Math. 15(1), 41\u201357 (2001)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"Harris, D.G.: Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 700\u2013724 (2019)","DOI":"10.1109\/FOCS.2019.00048"},{"issue":"2","key":"1_CR35","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A Israeli","year":"1986","unstructured":"Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett. 22(2), 77\u201380 (1986)","journal-title":"Inf. Process. Lett."},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Linial, N.: Distributive graph algorithms - global solutions from local data. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 331\u2013335 (1987)","DOI":"10.1109\/SFCS.1987.20"},{"issue":"1","key":"1_CR37","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1_CR38","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/BF01303516","volume":"13","author":"N Linial","year":"1993","unstructured":"Linial, N., Saks, M.: Low diameter graph decompositions. Combinatorica 13(4), 441\u2013454 (1993)","journal-title":"Combinatorica"},{"key":"1_CR39","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"1_CR40","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Peng, R., Xu, S.C.: Parallel graph decompositions using random shifts. In: Proceedings of the Symposium on Parallel Algorithms and Architecture (SPAA), pp. 196\u2013203 (2013)","DOI":"10.1145\/2486159.2486180"},{"issue":"6","key":"1_CR41","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1_CR42","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I Newman","year":"1991","unstructured":"Newman, I.: Private vs common random bits in communication complexity. Inf. Process. Lett. 39(2), 67\u201371 (1991)","journal-title":"Inf. Process. Lett."},{"key":"1_CR43","doi-asserted-by":"crossref","unstructured":"Panconesi, A., Srinivasan, A.: Improved distributed algorithms for coloring and network decomposition problems. In: Proceedings of the Symposium on Theory of Computation (STOC), pp. 581\u2013592 (1992)","DOI":"10.1145\/129712.129769"},{"key":"1_CR44","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"1_CR45","doi-asserted-by":"crossref","unstructured":"Rozho\u0148, V., Ghaffari, M.: Polylogarithmic-time deterministic network decomposition and distributed derandomization. In: Proceedings of the Symposium on Theory of Computation (STOC), pp. to appear, arXiv:1907.10937 (2020)","DOI":"10.1145\/3357713.3384298"},{"issue":"4","key":"1_CR46","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.ipl.2004.08.007","volume":"92","author":"A Windsor","year":"2004","unstructured":"Windsor, A.: A simple proof that finding a maximal independent set in a graph is in NC. Inf. Process. Lett. 92(4), 185\u2013187 (2004)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-54921-3_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T02:40:02Z","timestamp":1619232002000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-54921-3_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030549206","9783030549213"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-54921-3_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"28 July 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paderborn","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sirocco2020.cs.uni-paderborn.de\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"46% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}