{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T21:06:21Z","timestamp":1762808781576,"version":"3.40.3"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030249212"},{"type":"electronic","value":"9783030249229"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-24922-9_9","type":"book-chapter","created":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T10:04:49Z","timestamp":1562925889000},"page":"124-138","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Breaking the Linear-Memory Barrier in $$\\mathsf {MPC}$$: Fast $$\\mathsf {MIS}$$ on Trees with Strongly Sublinear Memory"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Brandt","sequence":"first","affiliation":[]},{"given":"Manuela","family":"Fischer","sequence":"additional","affiliation":[]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,13]]},"reference":[{"issue":"4","key":"9_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"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Andoni, A., Stein, C., Song, Z., Wang, Z., Zhong, P.: Parallel graph connectivity in log diameter rounds. In: The Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 674\u2013685 (2018)","DOI":"10.1109\/FOCS.2018.00070"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Andoni, A., Nikolov, A., Onak, K., Yaroslavtsev, G.: Parallel algorithms for geometric graph problems. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 574\u2013583 (2014)","DOI":"10.1145\/2591796.2591805"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Assadi, S., Sun, X., Weinstein, O.: Massively parallel algorithms for finding well-connected components in sparse graphs. arXiv e-prints (2018)","DOI":"10.1145\/3293611.3331596"},{"key":"9_CR5","unstructured":"Assadi, S.: Simple round compression for parallel vertex cover. arXiv preprint: 1709.04599 (2017). http:\/\/arxiv.org\/abs\/1709.04599"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Assadi, S., Bateni, M., Bernstein, A., Mirrokni, V.S., Stein, C.: Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, 6\u20139 January 2019, pp. 1616\u20131635 (2019)","DOI":"10.1137\/1.9781611975482.98"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S.: Randomized composable coresets for matching and vertex cover. In: The Proceedings of the Symposium on Parallel Algorithms and Architectures (SPAA), pp. 3\u201312 (2017)","DOI":"10.1145\/3087556.3087581"},{"issue":"3","key":"9_CR8","doi-asserted-by":"publisher","first-page":"20","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 (JACM) 63(3), 20 (2016)","journal-title":"J. ACM (JACM)"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Beame, P., Koutris, P., Suciu, D.: Skew in parallel query processing. In: Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 212\u2013223. ACM (2014)","DOI":"10.1145\/2594538.2594558"},{"issue":"6","key":"9_CR10","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/3125644","volume":"64","author":"P Beame","year":"2017","unstructured":"Beame, P., Koutris, P., Suciu, D.: Communication steps for parallel query processing. J. ACM (JACM) 64(6), 40 (2017)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"9_CR11","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J Beck","year":"1991","unstructured":"Beck, J.: An algorithmic approach to the Lov\u00e1sz local lemma. Random Struct. Algorithms 2(4), 343\u2013365 (1991)","journal-title":"Random Struct. Algorithms"},{"key":"9_CR12","unstructured":"Behnezhad, S., Derakhshan, M., Hajiaghayi, M.: Brief announcement: semi-MapReduce meets congested clique. arXiv preprint arXiv:1802.10297 (2018)"},{"key":"9_CR13","unstructured":"Behnezhad, S., Derakhshan, M., Hajiaghayi, M., Karp, R.M.: Massively parallel symmetry breaking on sparse graphs: MIS and maximal matching. CoRR abs\/1807.06701 (2018). http:\/\/arxiv.org\/abs\/1807.06701"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Brandt, S., Fischer, M., Uitto, J.: Breaking the linear-memory barrier in MPC: Fast MIS on trees with strongly sublinear memory. arXiv:1802.06748 (2018)","DOI":"10.1007\/978-3-030-24922-9_9"},{"key":"9_CR15","unstructured":"Brandt, S., Fischer, M., Uitto, J.: Matching and MIS for uniformly sparse graphs in the low-memory MPC model. CoRR abs\/1807.05374 (2018). http:\/\/arxiv.org\/abs\/1807.05374"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Ceccarello, M., Pietracaprina, A., Pucci, G., Upfal, E.: Space and time efficient parallel graph decomposition, clustering, and diameter approximation. In: The Proceedings of the Symposium on Parallel Algorithms and Architectures (SPAA), pp. 182\u2013191 (2015)","DOI":"10.1145\/2755573.2755591"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Chang, Y.J., Fischer, M., Ghaffari, M., Uitto, J., Zheng, Z.: The complexity of $$(\\delta +1)$$ coloring in congested clique, massively parallel computation, and centralized local computation. arXiv preprint arXiv:1808.08419 abs\/1808.08419 (2018). http:\/\/arxiv.org\/abs\/1808.08419","DOI":"10.1145\/3293611.3331607"},{"key":"9_CR18","unstructured":"Chitnis, L., Das Sarma, A., Machanavajjhala, A., Rastogi, V.: Finding connected components in map-reduce in logarithmic rounds. In: ICDE 2013, pp. 50\u201361. IEEE Computer Society (2013)"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In: Symposium on Theory of Computing, pp. 206\u2013219 (1986)","DOI":"10.1145\/12130.12151"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Czumaj, A., \u0141acki, J., Madry, A., Mitrovi\u0107, S., Onak, K., Sankowski, P.: Round compression for parallel matching algorithms. arXiv preprint: 1707.03478 (2017)","DOI":"10.1145\/3188745.3188764"},{"issue":"1","key":"9_CR21","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51(1), 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) (2016)","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Gouleakis, T., Konrad, C., Mitrovic, S., Rubinfeld, R.: Improved massively parallel computation algorithms for MIS, matching, and vertex cover. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC) (2018, to appear)","DOI":"10.1145\/3212734.3212743"},{"key":"9_CR24","unstructured":"Ghaffari, M., Kuhn, F., Uitto, J.: Personal communication (2019)"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Uitto, J.: Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In: the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1636\u20131653 (2019)","DOI":"10.1137\/1.9781611975482.99"},{"key":"9_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-25591-5_39","volume-title":"Algorithms and Computation","author":"MT Goodrich","year":"2011","unstructured":"Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the MapReduce framework. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 374\u2013383. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-25591-5_39"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Karloff, H., Suri, S., Vassilvitskii, S.: A model of computation for MapReduce. In: the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 938\u2013948 (2010)","DOI":"10.1137\/1.9781611973075.76"},{"issue":"3","key":"9_CR28","first-page":"14","volume":"2","author":"R Kumar","year":"2015","unstructured":"Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in MapReduce and streaming. ACM Trans. Parallel Comput. (TOPC) 2(3), 14 (2015)","journal-title":"ACM Trans. Parallel Comput. (TOPC)"},{"key":"9_CR29","doi-asserted-by":"crossref","unstructured":"Lattanzi, S., Moseley, B., Suri, S., Vassilvitskii, S.: Filtering: a method for solving graph problems in MapReduce. In: The Proceedings of the Symposium on Parallel Algorithms and Architectures (SPAA), pp. 85\u201394 (2011)","DOI":"10.1145\/1989493.1989505"},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R.: Brief announcement: exponential speed-up of local algorithms using non-local communication. In: 29th Symposium on Principles of Distributed Computing (PODC), Zurich, Switzerland, July 2010","DOI":"10.1145\/1835698.1835772"},{"key":"9_CR31","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R.: MIS on trees. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 41\u201348 (2011)","DOI":"10.1145\/1993806.1993813"},{"issue":"4","key":"9_CR32","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(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"9_CR33","unstructured":"Onak, K.: Round compression for parallel graph algorithms in strongly sublinear space. CoRR abs\/1807.08745 (2018). http:\/\/arxiv.org\/abs\/1807.08745"},{"key":"9_CR34","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 Computing (STOC), pp. 581\u2013592. ACM (1992)","DOI":"10.1145\/129712.129769"},{"key":"9_CR35","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: Fast distributed algorithms for connectivity and MST in large graphs. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 429\u2013438. ACM (2016)","DOI":"10.1145\/2935764.2935785"},{"key":"9_CR36","doi-asserted-by":"crossref","unstructured":"Pietracaprina, A., Pucci, G., Riondato, M., Silvestri, F., Upfal, E.: Space-round tradeoffs for MapReduce computations. In: Proceedings of the International Conference on Supercomputing, pp. 235\u2013244. ACM (2012)","DOI":"10.1145\/2304576.2304607"},{"key":"9_CR37","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., Vassilvitskii, S., Wang, J.R.: Shuffles and circuits: (on lower bounds for modern parallel computation). In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 1\u201312. ACM (2016)","DOI":"10.1145\/2935764.2935799"},{"key":"9_CR38","unstructured":"Yaroslavtsev, G., Vadapalli, A.: Massively parallel algorithms and hardness for single-linkage clustering under $$l_p$$ distances. In: Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, 10\u201315 July 2018, pp. 5596\u20135605 (2018)"}],"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-24922-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:57:23Z","timestamp":1710266243000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-24922-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030249212","9783030249229"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24922-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"13 July 2019","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":"L'Aquila","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cs.gssi.it\/sirocco2019\/","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":"39","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":"9","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":"49% - 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":"6","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)"}}]}}