{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T01:58:15Z","timestamp":1778551095132,"version":"3.51.4"},"reference-count":88,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["715672"],"award-info":[{"award-number":["715672"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003500","name":"Universit\u00e0 degli Studi di Padova","doi-asserted-by":"publisher","award":["BIRD197859\/19"],"award-info":[{"award-number":["BIRD197859\/19"]}],"id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>Massively Parallel Computation<\/jats:italic> (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attention over the past few years, especially in the context of classical graph problems. So far, the only way to argue lower bounds for this model is to condition on conjectures about the hardness of some specific problems, such as graph connectivity on promise graphs that are either one cycle or two cycles, usually called the <jats:italic>one cycle versus two cycles<\/jats:italic> problem. This is unlike the traditional arguments based on conjectures about complexity classes (e.g., <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {P}\\ne \\textsf {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>P<\/mml:mi>\n                    <mml:mo>\u2260<\/mml:mo>\n                    <mml:mi>NP<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>), which are often more robust in the sense that refuting them would lead to groundbreaking algorithms for a whole bunch of problems. In this paper we present connections between problems and classes of problems that allow the latter type of arguments. These connections concern the class of problems solvable in a sublogarithmic amount of rounds in the MPC model, denoted by <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {MPC}(o(\\log N))$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>MPC<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>o<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and the standard space complexity classes <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {L}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>L<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {NL}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NL<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and suggest conjectures that are robust in the sense that refuting them would lead to many surprisingly fast new algorithms in the MPC model. We also obtain new conditional lower bounds, and prove new reductions and equivalences between problems in the MPC model. Specifically, our main results are as follows.<jats:list list-type=\"bullet\">\n                <jats:list-item>\n                  <jats:p>Lower bounds conditioned on the one cycle versus two cycles conjecture can be instead argued under the <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {L}\\nsubseteq \\textsf {MPC}(o(\\log N))$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>L<\/mml:mi>\n                        <mml:mo>\u2288<\/mml:mo>\n                        <mml:mi>MPC<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>o<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>N<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula> conjecture: these two assumptions are equivalent, and refuting either of them would lead to <jats:inline-formula><jats:alternatives><jats:tex-math>$$o(\\log N)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>o<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>N<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-round MPC algorithms for a large number of challenging problems, including list ranking, minimum cut, and planarity testing. In fact, we show that these problems and many others require asymptotically the same number of rounds as the seemingly much easier problem of distinguishing between a graph being one cycle or two cycles.<\/jats:p>\n                <\/jats:list-item>\n                <jats:list-item>\n                  <jats:p>Many lower bounds previously argued under the one cycle versus two cycles conjecture can be argued under an even more robust (thus harder to refute) conjecture, namely <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {NL}\\nsubseteq \\textsf {MPC}(o(\\log N))$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>NL<\/mml:mi>\n                        <mml:mo>\u2288<\/mml:mo>\n                        <mml:mi>MPC<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>o<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>N<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Refuting this conjecture would lead to <jats:inline-formula><jats:alternatives><jats:tex-math>$$o(\\log N)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>o<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>N<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-round MPC algorithms for an even larger set of problems, including all-pairs shortest paths, betweenness centrality, and all aforementioned ones. Lower bounds under this conjecture hold for problems such as perfect matching and network flow.<\/jats:p>\n                <\/jats:list-item>\n              <\/jats:list><\/jats:p>","DOI":"10.1007\/s00446-021-00418-2","type":"journal-article","created":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T13:04:05Z","timestamp":1642683845000},"page":"165-183","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Equivalence classes and conditional hardness in massively parallel computations"],"prefix":"10.1007","volume":"35","author":[{"given":"Danupon","family":"Nanongkai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9108-2448","authenticated-orcid":false,"given":"Michele","family":"Scquizzato","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,20]]},"reference":[{"key":"418_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Grandoni, F., Vassilevska Williams, V.: Subcubic equivalences between graph centrality problems, APSP and diameter. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1681\u20131697 (2015)","DOI":"10.1137\/1.9781611973730.112"},{"key":"418_CR2","doi-asserted-by":"crossref","unstructured":"Adler, M. Dittrich, W. Juurlink, B.H.H., Kutylowski, M., Rieping, I.: Communication-optimal parallel minimum spanning tree algorithms. In: Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 27\u201336 (1998)","DOI":"10.1145\/277651.277662"},{"issue":"4","key":"418_CR3","first-page":"277","volume":"6","author":"FN Afrati","year":"2013","unstructured":"Afrati, F.N., Sarma, A.D., Salihoglu, S., Ullman, J.D.: Upper and lower bounds on the cost of a Map-Reduce computation. PVLDB 6(4), 277\u2013288 (2013)","journal-title":"PVLDB"},{"key":"418_CR4","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 459\u2013467 (2012)","DOI":"10.1137\/1.9781611973099.40"},{"issue":"1","key":"418_CR5","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.ic.2003.09.002","volume":"189","author":"E Allender","year":"2004","unstructured":"Allender, E., Mahajan, M.: The complexity of planarity testing. Inf. Comput. 189(1), 117\u2013134 (2004)","journal-title":"Inf. Comput."},{"issue":"2","key":"418_CR6","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/PL00001603","volume":"9","author":"C \u00c0lvarez","year":"2000","unstructured":"\u00c0lvarez, C., Greenlaw, R.: A compendium of problems complete for symmetric logarithmic space. Comput. Complex. 9(2), 123\u2013145 (2000)","journal-title":"Comput. Complex."},{"key":"418_CR7","doi-asserted-by":"crossref","unstructured":"Andoni, A., Nikolov, A., Onak, K., Yaroslavtsev, G.: Parallel algorithms for geometric graph problems. In: Proceedings of the 46th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 574\u2013583 (2014)","DOI":"10.1145\/2591796.2591805"},{"key":"418_CR8","doi-asserted-by":"crossref","unstructured":"Andoni, A., Stein, C., Song, Z., Wang, Z., Zhong, P.: Parallel graph connectivity in log diameter rounds. In: Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 674\u2013685 (2018)","DOI":"10.1109\/FOCS.2018.00070"},{"key":"418_CR9","unstructured":"Andoni, A., Stein, C., Zhong, P.: Log diameter rounds algorithms for $$2$$-vertex and $$2$$-edge connectivity. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 14:1\u201314:16 (2019)"},{"key":"418_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"418_CR11","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 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1616\u20131635 (2019)","DOI":"10.1137\/1.9781611975482.98"},{"key":"418_CR12","doi-asserted-by":"crossref","unstructured":"Assadi, S., Chen, Y., Khanna, Y.: Sublinear algorithms for ($$\\Delta $$+1) vertex coloring. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 767\u2013786 (2019)","DOI":"10.1137\/1.9781611975482.48"},{"key":"418_CR13","doi-asserted-by":"crossref","unstructured":"Assadi , S., Khanna, S.: Tight bounds on the round complexity of the distributed maximum coverage problem. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2412\u20132431 (2018)","DOI":"10.1137\/1.9781611975031.155"},{"key":"418_CR14","doi-asserted-by":"crossref","unstructured":"Assadi, S., Sun, X., Weinstein, O.: Massively parallel algorithms for finding well-connected components in sparse graphs. In: Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pp. 461\u2013470 (2019)","DOI":"10.1145\/3293611.3331596"},{"issue":"6","key":"418_CR15","doi-asserted-by":"publisher","first-page":"1","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 64(6), 1\u201358 (2017)","journal-title":"J. ACM"},{"issue":"3","key":"418_CR16","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1006\/jcss.1995.1035","volume":"50","author":"M Beaudry","year":"1995","unstructured":"Beaudry, M., McKenzie, P.: Circuits, matrices, and nonassociative computation. J. Comput. Syst. Sci. 50(3), 441\u2013455 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"418_CR17","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Brandt, S., Derakhshan, M., Fischer, M., Hajiaghayi, M., Karp, R.M., Uitto, J.: Massively parallel computation of matching and MIS in sparse graphs. In: Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pp. 481\u2013490 (2019)","DOI":"10.1145\/3293611.3331609"},{"key":"418_CR18","unstructured":"Behnezhad, S., Derakhshan, M., Hajiaghayi, M.: Semi-MapReduce meets congested clique. CoRR (2018). arXiv:1802.10297"},{"key":"418_CR19","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Dhulipala, L., Esfandiari, H., Lacki, J., Mirrokni, V.: Near-optimal massively parallel graph connectivity. In: Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1615\u20131636 (2019)","DOI":"10.1109\/FOCS.2019.00095"},{"issue":"13","key":"418_CR20","doi-asserted-by":"publisher","first-page":"3588","DOI":"10.14778\/3424573.3424579","volume":"13","author":"S Behnezhad","year":"2020","unstructured":"Behnezhad, S., Dhulipala, L., Esfandiari, H., Lacki, J., Mirrokni, V.S., Schudy, W.: Parallel graph algorithms in constant adaptive rounds: theory meets practice. Proc. VLDB Endow. 13(13), 3588\u20133602 (2020)","journal-title":"Proc. VLDB Endow."},{"key":"418_CR21","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Hajiaghayi, M., Harris, D.G.: Exponentially faster massively parallel maximal matching. In: Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1637\u20131649 (2019)","DOI":"10.1109\/FOCS.2019.00096"},{"issue":"3","key":"418_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3181776","volume":"4","author":"G Bilardi","year":"2018","unstructured":"Bilardi, G., Scquizzato, M., Silvestri, F.: A lower bound technique for communication in BSP. ACM Trans. Parallel Comput. 4(3), 1\u201327 (2018)","journal-title":"ACM Trans. Parallel Comput."},{"issue":"3","key":"418_CR23","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A Borodin","year":"1989","unstructured":"Borodin, A., Cook, S.A., Dymond, P.W., Ruzzo, W.L., Tompa, M.: Two applications of inductive counting for complementation problems. SIAM J. Comput. 18(3), 559\u2013578 (1989)","journal-title":"SIAM J. Comput."},{"key":"418_CR24","doi-asserted-by":"crossref","unstructured":"Boroujeni, M., Ehsani, S., Ghodsi, M., Hajiaghayi, M.T. , Seddighin, S.: Approximating edit distance in truly subquadratic time: quantum and MapReduce. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1170\u20131189 (2018)","DOI":"10.1137\/1.9781611975031.76"},{"key":"418_CR25","doi-asserted-by":"crossref","unstructured":"Buss, S.R.: The Boolean formula value problem is in ALOGTIME. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 123\u2013131 (1987)","DOI":"10.1145\/28395.28409"},{"issue":"2","key":"418_CR26","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"AK Chandra","year":"1984","unstructured":"Chandra, A.K., Stockmeyer, L.J., Vishkin, U.: Constant depth reducibility. SIAM J. Comput. 13(2), 423\u2013439 (1984)","journal-title":"SIAM J. Comput."},{"key":"418_CR27","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Fischer, M., Ghaffari, M., Uitto, J., Zheng, Y.: The complexity of ($$\\Delta $$+1) coloring in congested clique, massively parallel computation, and centralized local computation. In: Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pp. 471\u2013480 (2019)","DOI":"10.1145\/3293611.3331607"},{"key":"418_CR28","doi-asserted-by":"crossref","unstructured":"Chung, K., Ho, K., Sun, X.: On the hardness of massively parallel computation. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 153\u2013162 (2020)","DOI":"10.1145\/3350755.3400223"},{"issue":"1\u20133","key":"418_CR29","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"SA Cook","year":"1985","unstructured":"Cook, S.A.: A taxonomy of problems with fast parallel algorithms. Inf. Control 64(1\u20133), 2\u201322 (1985)","journal-title":"Inf. Control"},{"issue":"3","key":"418_CR30","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"SA Cook","year":"1987","unstructured":"Cook, S.A., McKenzie, P.: Problems complete for deterministic logarithmic space. J. Algorithms 8(3), 385\u2013394 (1987)","journal-title":"J. Algorithms"},{"key":"418_CR31","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Davies, P., Parter, M.: Component stability in low-space massively parallel computation. In: Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC), pp. 481\u2013491 (2021)","DOI":"10.1145\/3465084.3467903"},{"issue":"2","key":"418_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3451992","volume":"17","author":"A Czumaj","year":"2021","unstructured":"Czumaj, A., Davies, P., Parter, M.: Graph sparsification for derandomizing massively parallel computation with low space. ACM Trans. Algorithms 17(2), 1\u201327 (2021)","journal-title":"ACM Trans. Algorithms"},{"issue":"5","key":"418_CR33","doi-asserted-by":"publisher","first-page":"STOC18-1","DOI":"10.1137\/18M1197655","volume":"49","author":"A Czumaj","year":"2020","unstructured":"Czumaj, A., Lacki, J., Madry, A., Mitrovic, S., Onak, K., Sankowski, P.: Round compression for parallel matching algorithms. SIAM J. Comput. 49(5), STOC18-1 (2020)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"418_CR34","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1007\/s00224-013-9469-9","volume":"53","author":"B Das","year":"2013","unstructured":"Das, B., Datta, S., Nimbhorkar, P.: Log-space algorithms for paths and matchings in $$k$$-trees. Theory Comput. Syst. 53(4), 669\u2013689 (2013)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"418_CR35","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":"418_CR36","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Durfee, D., Kulkarni, J., Peng, R., Sawlani, S., Sun, X.: Parallel batch-dynamic graphs: algorithms and lower bounds. In: Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1300\u20131319 (2020)","DOI":"10.1137\/1.9781611975994.79"},{"key":"418_CR37","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC), pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"issue":"3","key":"418_CR38","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1997.1485","volume":"54","author":"K Etessami","year":"1997","unstructured":"Etessami, K.: Counting quantifiers, successor relations, and logarithmic space. J. Comput. Syst. Sci. 54(3), 400\u2013411 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"418_CR39","doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Meyer, A.R.: Boolean matrix multiplication and transitive closure. In: Proceedings of the 12th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 129\u2013131 (1971)","DOI":"10.1109\/SWAT.1971.4"},{"key":"418_CR40","doi-asserted-by":"crossref","unstructured":"Fish, B., Kun, J., Lelkes, \u00c1.D., Reyzin, L., Tur\u00e1n, G.: On the computational complexity of MapReduce. In: Proceedings of the 29th International Symposium on Distributed Computing (DISC), pp. 1\u201315 (2015)","DOI":"10.1007\/978-3-662-48653-5_1"},{"key":"418_CR41","unstructured":"Frei, F., Wada, K.: Efficient circuit simulation in MapReduce. In: Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC), pp. 52:1\u201352:21 (2019)"},{"key":"418_CR42","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 37th ACM Symposium on Principles of Distributed Computing (PODC), pp. 129\u2013138 (2018)","DOI":"10.1145\/3212734.3212743"},{"key":"418_CR43","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Uitto, J.: Conditional hardness results for massively parallel computation from distributed lower bounds. In: Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1650\u20131663 (2019)","DOI":"10.1109\/FOCS.2019.00097"},{"key":"418_CR44","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Nowicki, K.: Massively parallel algorithms for minimum cut. In: Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), pp. 119\u2013128 (2020)","DOI":"10.1145\/3382734.3405737"},{"key":"418_CR45","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Uitto, J.: Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In:Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1636\u20131653 (2019)","DOI":"10.1137\/1.9781611975482.99"},{"issue":"2","key":"418_CR46","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/S0097539795294141","volume":"29","author":"MT Goodrich","year":"1999","unstructured":"Goodrich, M.T.: Communication-efficient parallel sorting. SIAM J. Comput. 29(2), 416\u2013432 (1999)","journal-title":"SIAM J. Comput."},{"key":"418_CR47","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the MapReduce framework. In: Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC), pp. 374\u2013383 (2011)","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"418_CR48","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Seddighin, S., Sun, X.: Massively parallel approximation algorithms for edit distance and longest common subsequence. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1654\u20131672 (2019)","DOI":"10.1137\/1.9781611975482.100"},{"key":"418_CR49","doi-asserted-by":"crossref","unstructured":"Hegeman, J.W., Pandurangan, G., Pemmaraju, S.V., Sardeshmukh, V.B., Scquizzato, M.: Toward optimal bounds in the congested clique: graph connectivity and MST. In: Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC), pp. 91\u2013100 (2015)","DOI":"10.1145\/2767386.2767434"},{"key":"418_CR50","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/j.tcs.2015.09.029","volume":"608","author":"JW Hegeman","year":"2015","unstructured":"Hegeman, J.W., Pemmaraju, S.V.: Lessons from the congested clique applied to MapReduce. Theor. Comput. Sci. 608, 268\u2013281 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"418_CR51","unstructured":"Im, S.,Moseley, B.: A conditional lower bound on graph connectivity in MapReduce. CoRR (2019). arXiv: 1904.08954"},{"key":"418_CR52","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B., Sun, X.: Efficient massively parallel methods for dynamic programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 798\u2013811 (2017)","DOI":"10.1145\/3055399.3055460"},{"key":"418_CR53","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Springer, Berlin (1999)"},{"key":"418_CR54","doi-asserted-by":"crossref","unstructured":"Isard, M., Budiu, M., Yu, Y., Birrell, A.,Fetterly, D.: Dryad: distributed data-parallel programs from sequential building blocks. In: Proceedings of the 2007 EuroSys Conference, pp. 59\u201372 (2007)","DOI":"10.1145\/1272998.1273005"},{"key":"418_CR55","doi-asserted-by":"crossref","unstructured":"Jacob, R., Lieber, T., Sitchinava, N.: On the complexity of list ranking in the parallel external memory model. In: Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 384\u2013395 (2014)","DOI":"10.1007\/978-3-662-44465-8_33"},{"issue":"1","key":"418_CR56","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"ND Jones","year":"1975","unstructured":"Jones, N.D.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11(1), 68\u201385 (1975)","journal-title":"J. Comput. Syst. Sci."},{"key":"418_CR57","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"ND Jones","year":"1976","unstructured":"Jones, N.D., Lien, Y.E., Laaser, W.T.: New problems complete for nondeterministic log space. Math. Syst. Theory 10, 1\u201317 (1976)","journal-title":"Math. Syst. Theory"},{"key":"418_CR58","unstructured":"Karger, D.R.: Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 21\u201330 (1993)"},{"key":"418_CR59","doi-asserted-by":"crossref","unstructured":"Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for MapReduce. In: Proceedings of the 21st annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 938\u2013948 (2010)","DOI":"10.1137\/1.9781611973075.76"},{"key":"418_CR60","doi-asserted-by":"crossref","unstructured":"Kiveris, R., Lattanzi, S., Mirrokni, V.S., Rastogi, V., Vassilvitskii, S.: Connected components in MapReduce and beyond. In: Proceedings of the ACM Symposium on Cloud Computing (SoCC), pp. 18:1\u201318:13 (2014)","DOI":"10.1145\/2670979.2670997"},{"key":"418_CR61","doi-asserted-by":"crossref","unstructured":"Klauck, H., Nanongkai, D., Pandurangan, G.,Robinson, P.: Distributed computation of large-scale graph problems. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 391\u2013410 (2015)","DOI":"10.1137\/1.9781611973730.28"},{"key":"418_CR62","doi-asserted-by":"crossref","unstructured":"Korhonen, J.H., Suomela, J.: Towards a complexity theory for the congested clique. In: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 163\u2013172 (2018)","DOI":"10.1145\/3210377.3210391"},{"issue":"3","key":"418_CR63","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2809814","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. 2(3), 1\u201322 (2015)","journal-title":"ACM Trans. Parallel Comput."},{"key":"418_CR64","doi-asserted-by":"crossref","unstructured":"Lacki, J., Mitrovic, S., Onak, K., Sankowski,P.: Walking randomly, massively, and efficiently. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 364\u2013377 (2020)","DOI":"10.1145\/3357713.3384303"},{"key":"418_CR65","doi-asserted-by":"crossref","unstructured":"Lattanzi, S., Moseley, B., Suri, S., Vassilvitskii, S.: Filtering: a method for solving graph problems in MapReduce. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 85\u201394 (2011)","DOI":"10.1145\/1989493.1989505"},{"key":"418_CR66","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0304-3975(82)90058-5","volume":"19","author":"HR Lewis","year":"1982","unstructured":"Lewis, H.R., Papadimitriou, C.H.: Symmetric space-bounded computation. Theor. Comput. Sci. 19, 161\u2013187 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"418_CR67","doi-asserted-by":"crossref","unstructured":"MacKenzie, P.D., Ramachandran, V.: Computational bounds for fundamental problems on general-purpose parallel models. In: Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 152\u2013163 (1998)","DOI":"10.1145\/277651.277681"},{"key":"418_CR68","unstructured":"Nanongkai, D., Scquizzato, M.: Equivalence classes and conditional hardness in massively parallel computations. In: Proceedings of the 23rd International Conference on Principles of Distributed Systems (OPODIS), pp. 33:1\u201333:16 (2019)"},{"key":"418_CR69","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ta-Shma, A.: Symmetric logspace is closed under complement. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pp. 140\u2013146 (1995)","DOI":"10.1145\/225058.225101"},{"key":"418_CR70","unstructured":"Onak, K.: Personal communication (2019)"},{"issue":"1","key":"418_CR71","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3209689","volume":"5","author":"G Pandurangan","year":"2018","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: Fast distributed algorithms for connectivity and MST in large graphs. ACM Trans. Parallel Comput. 5(1), 1\u201322 (2018)","journal-title":"ACM Trans. Parallel Comput."},{"issue":"2","key":"418_CR72","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3460900","volume":"8","author":"G Pandurangan","year":"2021","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: On the distributed complexity of large-scale graph computations. ACM Trans. Parallel Comput. 8(2), 1\u201328 (2021)","journal-title":"ACM Trans. Parallel Comput."},{"key":"418_CR73","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Boston (1994)"},{"key":"418_CR74","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 26th International Conference on Supercomputing (ICS), pp. 235\u2013244 (2012)","DOI":"10.1145\/2304576.2304607"},{"key":"418_CR75","doi-asserted-by":"crossref","unstructured":"Rastogi, V., Machanavajjhala, A., Chitnis, L., Sarma, A.D.: Finding connected components in Map-Reduce in logarithmic rounds. In: Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE), pp. 50\u201361 (2013)","DOI":"10.1109\/ICDE.2013.6544813"},{"issue":"4","key":"418_CR76","doi-asserted-by":"publisher","first-page":"17:1-","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17:1--17:24 (2008)","journal-title":"J. ACM"},{"key":"418_CR77","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.P.: Pseudorandom walks on regular digraphs and the RL vs. L problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 457\u2013466 (2006)","DOI":"10.1145\/1132516.1132583"},{"issue":"6","key":"418_CR78","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3232536","volume":"65","author":"T Roughgarden","year":"2018","unstructured":"Roughgarden, T., Vassilvitskii, S., Wang, J.R.: Shuffles and circuits (on lower bounds for modern parallel computation). J. ACM 65(6), 1\u201324 (2018)","journal-title":"J. ACM"},{"issue":"2","key":"418_CR79","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"418_CR80","unstructured":"Scquizzato, M.,Silvestri, F.: Communication lower bounds for distributed-memory computations. In: Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 627\u2013638 (2014)"},{"key":"418_CR81","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"1997","unstructured":"Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997)"},{"key":"418_CR82","doi-asserted-by":"crossref","unstructured":"Svensson, O., Tarnawski, J.: The matching problem in general graphs is in quasi-NC. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 696\u2013707 (2017)","DOI":"10.1109\/FOCS.2017.70"},{"issue":"8","key":"418_CR83","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"},{"key":"418_CR84","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V.: On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians 2018 (ICM 2018), pp. 3431\u20133472 (2018)","DOI":"10.1142\/9789813272880_0188"},{"issue":"5","key":"418_CR85","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3186893","volume":"65","author":"V Vassilevska Williams","year":"2018","unstructured":"Vassilevska Williams, V., Williams, R.R.: Subcubic equivalences between path, matrix, and triangle problems. J. ACM 65(5), 1\u201338 (2018)","journal-title":"J. ACM"},{"key":"418_CR86","volume-title":"Hadoop: The Definitive Guide","author":"T White","year":"2012","unstructured":"White, T.: Hadoop: The Definitive Guide. O\u2019Reilly Media, Inc., Sebastopol (2012)"},{"key":"418_CR87","unstructured":"Yaroslavtsev, G., Vadapalli, A.: Massively parallel algorithms and hardness for single-linkage clustering under $$\\ell _p$$-distances. In: Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 5596\u20135605 (2018)"},{"issue":"11","key":"418_CR88","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/2934664","volume":"59","author":"M Zaharia","year":"2016","unstructured":"Zaharia, M., Xin, R.S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M.J., Ghodsi, A., Gonzalez, J., Shenker, S., Stoica, I.: Apache Spark: a unified engine for big data processing. Commun. ACM 59(11), 56\u201365 (2016)","journal-title":"Commun. ACM"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00418-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-021-00418-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00418-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,10]],"date-time":"2022-03-10T03:03:23Z","timestamp":1646881403000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-021-00418-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,20]]},"references-count":88,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["418"],"URL":"https:\/\/doi.org\/10.1007\/s00446-021-00418-2","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,20]]},"assertion":[{"value":"28 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}