{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:12:37Z","timestamp":1775067157939,"version":"3.50.1"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:00:00Z","timestamp":1742947200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:00:00Z","timestamp":1742947200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002744","name":"Bar-Ilan University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002744","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Massively-parallel graph algorithms have received extensive attention over the past decade, with research focusing on three memory regimes: the superlinear regime, the near-linear regime, and the sublinear regime. The sublinear regime is the most desirable in practice, but conditional hardness results point towards its limitations. In this work we study a <jats:italic>heterogeneous<\/jats:italic> model, where the memory of the machines varies in size. We focus mostly on the heterogeneous setting created by adding a single near-linear machine to the sublinear MPC regime, and show that even a single large machine suffices to circumvent most of the conditional hardness results for the sublinear regime: for graphs with <jats:italic>n<\/jats:italic> vertices and <jats:italic>m<\/jats:italic> edges, we give (a) an MST algorithm that runs in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(\\log \\log (m\/n))$$<\/jats:tex-math>\n                <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:mo>log<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> rounds; (b) an algorithm that constructs an <jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic>)-spanner of size <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(n^{1+1\/k})$$<\/jats:tex-math>\n                <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:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> in <jats:italic>O<\/jats:italic>(1) rounds; and (c) a maximal-matching algorithm that runs in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(\\sqrt{\\log (m\/n)}\\log \\log (m\/n))$$<\/jats:tex-math>\n                <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:msqrt>\n                      <mml:mrow>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>m<\/mml:mi>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msqrt>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>m<\/mml:mi>\n                      <mml:mo>\/<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> rounds. We also observe that the best known near-linear MPC algorithms for several other graph problems which are conjectured to be hard in the sublinear regime (minimum cut, maximal independent set, and vertex coloring) can easily be transformed to work in the heterogeneous MPC model with a single near-linear machine, while retaining their original round complexity in the near-linear regime. If the large machine is allowed to have <jats:italic>superlinear<\/jats:italic> memory, all of the problems above can be solved in <jats:italic>O<\/jats:italic>(1) rounds.<\/jats:p>","DOI":"10.1007\/s00446-025-00479-7","type":"journal-article","created":{"date-parts":[[2025,3,29]],"date-time":"2025-03-29T16:28:11Z","timestamp":1743265691000},"page":"185-206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Massively parallel computation in a heterogeneous regime"],"prefix":"10.1007","volume":"38","author":[{"given":"Orr","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adi","family":"Horowitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rotem","family":"Oshman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,3,26]]},"reference":[{"key":"479_CR1","doi-asserted-by":"crossref","unstructured":"Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for mapreduce. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 938\u2013948 (2010)","DOI":"10.1137\/1.9781611973075.76"},{"key":"479_CR2","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the mapreduce framework. In: Algorithms and Computation - 22nd International Symposium, ISAAC. Lecture Notes in Computer Science, vol. 7074, pp. 374\u2013383 (2011)","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"479_CR3","doi-asserted-by":"crossref","unstructured":"Lattanzi, S., Moseley, B., Suri, S., Vassilvitskii, S.: Filtering: a method for solving graph problems in mapreduce. In: SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 85\u201394 (2011)","DOI":"10.1145\/1989493.1989505"},{"key":"479_CR4","doi-asserted-by":"crossref","unstructured":"Andoni, A., Nikolov, A., Onak, K., Yaroslavtsev, G.: Parallel algorithms for geometric graph problems. In: Symposium on Theory of Computing, STOC, pp. 574\u2013583 (2014)","DOI":"10.1145\/2591796.2591805"},{"issue":"6","key":"479_CR5","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 64(6), 40\u201314058 (2017)","journal-title":"J. ACM"},{"key":"479_CR6","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Davies, P., Parter, M.: Improved deterministic ($$\\Delta $$+1) coloring in low-space MPC. In: PODC: ACM Symposium on Principles of Distributed Computing, pp. 469\u2013479 (2021)","DOI":"10.1145\/3465084.3467937"},{"key":"479_CR7","doi-asserted-by":"crossref","unstructured":"Andoni, A., Song, Z., Stein, C., Wang, Z., Zhong, P.: Parallel graph connectivity in log diameter rounds. In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 674\u2013685 (2018)","DOI":"10.1109\/FOCS.2018.00070"},{"key":"479_CR8","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Dhulipala, L., Esfandiari, H., Lacki, J., Mirrokni, V.S.: Near-optimal massively parallel graph connectivity. In: 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 1615\u20131636 (2019)","DOI":"10.1109\/FOCS.2019.00095"},{"key":"479_CR9","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 Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1636\u20131653 (2019)","DOI":"10.1137\/1.9781611975482.99"},{"key":"479_CR10","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Hajiaghayi, M., Harris, D.G.: Exponentially faster massively parallel maximal matching. In: 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 1637\u20131649 (2019)","DOI":"10.1109\/FOCS.2019.00096"},{"key":"479_CR11","doi-asserted-by":"crossref","unstructured":"Bamberger, P., Kuhn, F., Maus, Y.: Efficient deterministic distributed coloring with small bandwidth. In: PODC \u201920: ACM Symposium on Principles of Distributed Computing, pp. 243\u2013252 (2020)","DOI":"10.1145\/3382734.3404504"},{"key":"479_CR12","unstructured":"Ghaffari, M., Lattanzi, S., Mitrovic, S.: Improved parallel algorithms for density-based network clustering. In: Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA. Proceedings of Machine Learning Research, vol. 97, pp. 2201\u20132210 (2019)"},{"key":"479_CR13","unstructured":"Kothapalli, K., Pai, S., Pemmaraju, S.V.: Sample-and-gather: Fast ruling set algorithms in the low-memory MPC model. In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS. LIPIcs, vol. 182, pp. 28\u201312818 (2020)"},{"key":"479_CR14","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Jin, C., Nilis, D.: A massively parallel algorithm for minimum weight vertex cover. In: SPAA: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 259\u2013268 (2020)","DOI":"10.1145\/3350755.3400260"},{"key":"479_CR15","unstructured":"Ghaffari, M., Grunau, C., Jin, C.: Improved mpc algorithms for mis, matching, and coloring on trees and beyond. In: 34th International Symposium on Distributed Computing, DISC. LIPIcs, vol. 179, pp. 34\u201313418 (2020)"},{"key":"479_CR16","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 2019 ACM Symposium on Principles of Distributed Computing. PODC \u201919, pp. 471\u2013480 (2019)","DOI":"10.1145\/3293611.3331607"},{"key":"479_CR17","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 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, pp. 129\u2013138 (2018)","DOI":"10.1145\/3212734.3212743"},{"key":"479_CR18","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Uitto, J.: Conditional hardness results for massively parallel computation from distributed lower bounds. In: 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 1650\u20131663 (2019)","DOI":"10.1109\/FOCS.2019.00097"},{"key":"479_CR19","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Nowicki, K., Thorup, M.: Faster algorithms for edge connectivity via random 2-out contractions. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1260\u20131279 (2020)","DOI":"10.1137\/1.9781611975994.77"},{"key":"479_CR20","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Nowicki, K.: Massively parallel algorithms for minimum cut. In: PODC: ACM Symposium on Principles of Distributed Computing, pp. 119\u2013128 (2020)","DOI":"10.1145\/3382734.3405737"},{"issue":"2","key":"479_CR21","doi-asserted-by":"publisher","first-page":"16","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), 16\u201311627 (2021)","journal-title":"ACM Trans. Algorithms"},{"key":"479_CR22","doi-asserted-by":"crossref","unstructured":"Dory, M., Fischer, O., Khoury, S., Leitersdorf, D.: Constant-round spanners and shortest paths in congested clique and MPC. In: PODC \u201921: ACM Symposium on Principles of Distributed Computing, pp. 223\u2013233 (2021)","DOI":"10.1145\/3465084.3467928"},{"key":"479_CR23","doi-asserted-by":"crossref","unstructured":"Biswas, A.S., Dory, M., Ghaffari, M., Mitrovic, S., Nazari, Y.: Massively parallel algorithms for distance approximation and spanners. In: SPAA \u201921: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 118\u2013128 (2021)","DOI":"10.1145\/3409964.3461784"},{"key":"479_CR24","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 2019 ACM Symposium on Principles of Distributed Computing, PODC, pp. 481\u2013490 (2019)","DOI":"10.1145\/3293611.3331609"},{"key":"479_CR25","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Lacki, J., Madry, A., Mitrovic, S., Onak, K., Sankowski, P.: Round compression for parallel matching algorithms. SIAM J. Comput. 49(5) (2020)","DOI":"10.1137\/18M1197655"},{"key":"479_CR26","unstructured":"Nanongkai, D., Scquizzato, M.: Equivalence classes and conditional hardness in massively parallel computations. In: 23rd International Conference on Principles of Distributed Systems OPODIS. LIPIcs, vol. 153, pp. 33\u201313316 (2019)"},{"key":"479_CR27","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Davies, P., Parter, M.: Component stability in low-space massively parallel computation. In: PODC: ACM Symposium on Principles of Distributed Computing, pp. 481\u2013491 (2021)","DOI":"10.1145\/3465084.3467903"},{"key":"479_CR28","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 459\u2013467 (2012)","DOI":"10.1137\/1.9781611973099.40"},{"issue":"2","key":"479_CR29","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/3460890","volume":"8","author":"B Geissmann","year":"2021","unstructured":"Geissmann, B., Gianinazzi, L.: Parallel minimum cuts in near-linear work and low depth. ACM Trans. Parallel Comput. 8(2), 8\u20131820 (2021)","journal-title":"ACM Trans. Parallel Comput."},{"key":"479_CR30","doi-asserted-by":"crossref","unstructured":"Assadi, S., Chen, Y., Khanna, S.: Sublinear algorithms for ($$\\Delta $$ + 1) vertex coloring. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 767\u2013786 (2019)","DOI":"10.1137\/1.9781611975482.48"},{"issue":"2","key":"479_CR31","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"DR Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42(2), 321\u2013328 (1995)","journal-title":"J. ACM"},{"key":"479_CR32","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pp. 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"479_CR33","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 2015 ACM Symposium on Principles of Distributed Computing, PODC, pp. 91\u2013100 (2015)","DOI":"10.1145\/2767386.2767434"},{"key":"479_CR34","unstructured":"Nowicki, K.: Random sampling applied to the MST problem in the node congested clique model. CoRR abs\/1807.08738 (2018) 1807.08738"},{"key":"479_CR35","unstructured":"Pemmaraju, S.V., Sardeshmukh, V.B.: Super-fast MST algorithms in the congested clique using o(m) messages. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS. LIPIcs, vol. 65, pp. 47\u201314715 (2016)"},{"key":"479_CR36","doi-asserted-by":"crossref","unstructured":"Jurdzinski, T., Nowicki, K.: Mst in o(1) rounds of congested clique. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 2620\u20132632 (2018)","DOI":"10.1137\/1.9781611975031.167"},{"issue":"6","key":"479_CR37","doi-asserted-by":"publisher","first-page":"41","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), 41\u201314124 (2018)","journal-title":"J. ACM"},{"key":"479_CR38","unstructured":"Frei, F., Wada, K.: Efficient circuit simulation in mapreduce. In: 30th International Symposium on Algorithms and Computation (ISAAC), vol. 149, pp. 52\u201315221 (2019)"},{"issue":"3","key":"479_CR39","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/3470631","volume":"8","author":"S Behnezhad","year":"2021","unstructured":"Behnezhad, S., Dhulipala, L., Esfandiari, H., Lacki, J., Mirrokni, V.S., Schudy, W.: Massively parallel computation via remote memory access. ACM Trans. Parallel Comput. 8(3), 13\u201311325 (2021)","journal-title":"ACM Trans. Parallel Comput."},{"key":"479_CR40","unstructured":"Dinitz, M., Nazari, Y.: Distributed approximate distance oracles. CoRR abs\/1810.09027 (2018) 1810.09027"},{"key":"479_CR41","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Pavlov, E., Patt-Shamir, B., Peleg, D.: MST construction in $$o(\\log \\log {n})$$ communication rounds. In: SPAA: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 94\u2013100 (2003)","DOI":"10.1145\/777412.777428"},{"issue":"1","key":"479_CR42","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M Katz","year":"2004","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34(1), 23\u201340 (2004)","journal-title":"SIAM J. Comput."},{"key":"479_CR43","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. In: Graph-Theoretic Concepts in Computer Science, 25th International Workshop, WG. Lecture Notes in Computer Science, vol. 1665, pp. 30\u201341 (1999)","DOI":"10.1007\/3-540-46784-X_5"},{"issue":"1","key":"479_CR44","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discret. Comput. Geom. 9(1), 81\u2013100 (1993)","journal-title":"Discret. Comput. Geom."},{"key":"479_CR45","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Theory Of Graphs And Its Applications, Proceedings of Symposium Smolenice, pp. 29\u201336 (1964). Publ. House Cszechoslovak Acad. Sci., Prague"},{"key":"479_CR46","doi-asserted-by":"publisher","first-page":"100253","DOI":"10.1016\/j.cosrev.2020.100253","volume":"37","author":"AR Ahmed","year":"2020","unstructured":"Ahmed, A.R., Bodwin, G., Sahneh, F.D., Hamm, K., Jebelli, M.J.L., Kobourov, S.G., Spence, R.: Graph spanners: a tutorial review. Comput. Sci. Rev. 37, 100253 (2020)","journal-title":"Comput. Sci. Rev."},{"issue":"4","key":"479_CR47","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1002\/rsa.20130","volume":"30","author":"S Baswana","year":"2007","unstructured":"Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30(4), 532\u2013563 (2007)","journal-title":"Random Struct. Algorithms"},{"key":"479_CR48","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Fineman, J.T., Shun, J.: Greedy sequential maximal independent set and matching are parallel on average. In: Blelloch, G.E., Herlihy, M. (eds.) 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 308\u2013317. ACM, (2012)","DOI":"10.1145\/2312005.2312058"},{"key":"479_CR49","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Hajiaghayi, M., Harris, D.G.: Exponentially faster massively parallel maximal matching. In: Zuckerman, D. (ed.) 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1637\u20131649. IEEE Computer Society, (2019)","DOI":"10.1109\/FOCS.2019.00096"},{"issue":"7","key":"479_CR50","doi-asserted-by":"publisher","first-page":"1980","DOI":"10.1007\/s00453-021-00816-9","volume":"83","author":"KJ Ahn","year":"2021","unstructured":"Ahn, K.J., Cormode, G., Guha, S., McGregor, A., Wirth, A.: Correlation clustering in data streams. Algorithmica 83(7), 1980\u20132017 (2021)","journal-title":"Algorithmica"},{"key":"479_CR51","doi-asserted-by":"crossref","unstructured":"Assadi, S., Onak, K., Schieber, B., Solomon, S.: Fully dynamic maximal independent set with sublinear in n update time. In: Chan, T.M. (ed.) Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1919\u20131936. SIAM, (2019)","DOI":"10.1137\/1.9781611975482.116"},{"key":"479_CR52","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Lacki, J., Mirrokni, V.S.: Fully dynamic matching: Beating 2-approximation in $$\\Delta ^\\epsilon $$ update time. In: Symposium on Discrete Algorithms (SODA), pp. 2492\u20132508 (2020)","DOI":"10.1137\/1.9781611975994.152"},{"key":"479_CR53","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Saglam, M., Tardos, G.: Tight bounds for lp samplers, finding duplicates in streams, and related problems. In: Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pp. 49\u201358 (2011)","DOI":"10.1145\/1989284.1989289"},{"key":"479_CR54","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Lee, Y.T., Musco, C., Musco, C., Sidford, A.: Single pass spectral sparsification in dynamic streams. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 561\u2013570 (2014)","DOI":"10.1109\/FOCS.2014.66"},{"key":"479_CR55","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Woodruff, D.P.: Spanners and sparsifiers in dynamic streams. In: ACM Symposium on Principles of Distributed Computing, PODC \u201914, pp. 272\u2013281 (2014)","DOI":"10.1145\/2611462.2611497"},{"key":"479_CR56","doi-asserted-by":"crossref","unstructured":"McGregor, A., Tench, D., Vorotnikova, S., Vu, H.T.: Densest subgraph in dynamic graph streams. In: Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS Proceedings, Part II. Lecture Notes in Computer Science, vol. 9235, pp. 472\u2013482 (2015)","DOI":"10.1007\/978-3-662-48054-0_39"},{"key":"479_CR57","unstructured":"Biswas, A.S., Eden, T., Liu, Q.C., Rubinfeld, R., Mitrovic, S.: Massively parallel algorithms for small subgraph counting. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM), vol. 245, pp. 39\u201313928 (2022)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00479-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00479-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00479-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T08:27:38Z","timestamp":1757147258000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00479-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,26]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["479"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00479-7","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,26]]},"assertion":[{"value":"15 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest. Data sharing not applicable to this article as no datasets were generated or analysed during the current study.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}