{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:23:23Z","timestamp":1772119403442,"version":"3.50.1"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T00:00:00Z","timestamp":1690761600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T00:00:00Z","timestamp":1690761600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008047","name":"Carnegie Mellon University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008047","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2023,12]]},"abstract":"Abstract<\/jats:title>\n \n In this paper, we refine the (almost)\n existentially optimal<\/jats:italic>\n distributed Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS \u201821) into an (almost)\n universally optimal<\/jats:italic>\n distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an\n n<\/jats:italic>\n -node graph with\n shortcut quality<\/jats:italic>\n \n \n $$\\textrm{SQ}(G)$$<\/jats:tex-math>\n \n \n SQ<\/mml:mtext>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n can be solved after\n \n \n $$n^{o(1)} \\text {SQ}(G) \\log (1\/\\epsilon )$$<\/jats:tex-math>\n \n \n \n n<\/mml:mi>\n \n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n SQ<\/mml:mtext>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n log<\/mml:mo>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \u03f5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds, where\n \n \n $$\\epsilon >0$$<\/jats:tex-math>\n \n \n \u03f5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on\n G<\/jats:italic>\n requires\n \n \n $$\\widetilde{\\Omega }(\\textrm{SQ}(G))$$<\/jats:tex-math>\n \n \n \n \u03a9<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n SQ<\/mml:mtext>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds, even for a crude solution with\n \n \n $$\\epsilon \\le 1\/2$$<\/jats:tex-math>\n \n \n \u03f5<\/mml:mi>\n \u2264<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in\n \n \n $$D \\cdot n^{o(1)} \\log (1\/\\epsilon )$$<\/jats:tex-math>\n \n \n D<\/mml:mi>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \u03f5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds, where\n D<\/jats:italic>\n is the hop-diameter of the network; as well as\n \n \n $$n^{o(1)} \\log (1\/\\epsilon )$$<\/jats:tex-math>\n \n \n \n n<\/mml:mi>\n \n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \u03f5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -round algorithms for the case of\n \n \n $$\\textrm{SQ}(G) \\le n^{o(1)}$$<\/jats:tex-math>\n \n \n SQ<\/mml:mtext>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2264<\/mml:mo>\n \n n<\/mml:mi>\n \n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , which holds for most networks of interest. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated clique model. In this model, we show the existence of a Laplacian solver with round complexity\n \n \n $$n^{o(1)} \\log (1\/\\epsilon )$$<\/jats:tex-math>\n \n \n \n n<\/mml:mi>\n \n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \u03f5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . The unifying thread of these results, and our main technical contribution, is the development of near-optimal algorithms for a novel\n \n \n $$\\rho $$<\/jats:tex-math>\n \n \u03c1<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n congested<\/jats:italic>\n generalization of the standard\n part-wise aggregation<\/jats:italic>\n problem, which could be of independent interest.\n <\/jats:p>","DOI":"10.1007\/s00446-023-00454-0","type":"journal-article","created":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T06:02:13Z","timestamp":1690783333000},"page":"475-499","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts"],"prefix":"10.1007","volume":"36","author":[{"given":"Ioannis","family":"Anagnostides","sequence":"first","affiliation":[]},{"given":"Christoph","family":"Lenzen","sequence":"additional","affiliation":[]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[]},{"given":"Goran","family":"Zuzic","sequence":"additional","affiliation":[]},{"given":"Themis","family":"Gouleakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,31]]},"reference":[{"issue":"3","key":"454_CR1","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/090771430","volume":"35","author":"DA Spielman","year":"2014","unstructured":"Spielman, D.A., Teng, S.: Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Anal. Appl. 35(3), 835\u2013885 (2014). https:\/\/doi.org\/10.1137\/090771430","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"1","key":"454_CR2","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1137\/110845914","volume":"43","author":"I Koutis","year":"2014","unstructured":"Koutis, I., Miller, G.L., Peng, R.: Approaching optimality for solving SDD linear systems. SIAM J. Comput. 43(1), 337\u2013354 (2014). https:\/\/doi.org\/10.1137\/110845914","journal-title":"SIAM J. Comput."},{"key":"454_CR3","doi-asserted-by":"publisher","unstructured":"Kelner, J.A., Orecchia, L., Sidford, A., Zhu, Z.A.: A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In: Symposium on Theory of Computing Conference, STOC\u201913, 2013, pp. 911\u2013920 (2013). https:\/\/doi.org\/10.1145\/2488608.2488724","DOI":"10.1145\/2488608.2488724"},{"key":"454_CR4","doi-asserted-by":"publisher","unstructured":"Kyng, R., Sachdeva, S.: Approximate gaussian elimination for Laplacians - fast, sparse, and simple. In: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pp. 573\u2013582 (2016). https:\/\/doi.org\/10.1109\/FOCS.2016.68","DOI":"10.1109\/FOCS.2016.68"},{"key":"454_CR5","doi-asserted-by":"publisher","unstructured":"Axiotis, K., Madry, A., Vladu, A.: Faster sparse minimum cost flow by electrical flow localization. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pp. 528\u2013539 (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00059","DOI":"10.1109\/FOCS52979.2021.00059"},{"key":"454_CR6","doi-asserted-by":"publisher","unstructured":"Madry, A.: Computing maximum flow with augmenting electrical flows. In: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pp. 593\u2013602 (2016). https:\/\/doi.org\/10.1109\/FOCS.2016.70","DOI":"10.1109\/FOCS.2016.70"},{"key":"454_CR7","doi-asserted-by":"publisher","unstructured":"Brand, J., Lee, Y.T., Nanongkai, D., Peng, R., Saranurak, T., Sidford, A., Song, Z., Wang, D.: Bipartite matching in nearly-linear time on moderately dense graphs. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pp. 919\u2013930 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00090","DOI":"10.1109\/FOCS46700.2020.00090"},{"key":"454_CR8","doi-asserted-by":"publisher","unstructured":"Kelner, J.A., Lee, Y.T., Orecchia, L., Sidford, A.: An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 217\u2013226 (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.16","DOI":"10.1137\/1.9781611973402.16"},{"key":"454_CR9","doi-asserted-by":"publisher","unstructured":"Peng, R.: Approximate undirected maximum flows in $$O$$($$m$$polylog($$n$$)) time. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 1862\u20131867 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch130","DOI":"10.1137\/1.9781611974331.ch130"},{"key":"454_CR10","doi-asserted-by":"publisher","unstructured":"Axiotis, K., Madry, A., Vladu, A.: Circulation control for faster minimum cost flow in unit-capacity graphs. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pp. 93\u2013104 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00018","DOI":"10.1109\/FOCS46700.2020.00018"},{"key":"454_CR11","doi-asserted-by":"publisher","unstructured":"Forster, S., Goranci, G., Liu, Y.P., Peng, R., Sun, X., Ye, M.: Minor sparsifiers and the distributed laplacian paradigm. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pp. 989\u2013999 (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00099","DOI":"10.1109\/FOCS52979.2021.00099"},{"key":"454_CR12","doi-asserted-by":"publisher","unstructured":"Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing. STOC \u201911, pp. 363\u2013372 (2011). https:\/\/doi.org\/10.1145\/1993636.1993686","DOI":"10.1145\/1993636.1993686"},{"key":"454_CR13","doi-asserted-by":"publisher","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed mst construction. In: 40th Annual Symposium on Foundations of Computer Science, pp. 253\u2013261 (1999). https:\/\/doi.org\/10.1109\/SFFCS.1999.814597","DOI":"10.1109\/SFFCS.1999.814597"},{"key":"454_CR14","doi-asserted-by":"publisher","unstructured":"Elkin, M.: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing. STOC \u201904, pp. 331\u2013340 (2004). https:\/\/doi.org\/10.1145\/1007352.1007407","DOI":"10.1145\/1007352.1007407"},{"key":"454_CR15","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks II: low-congestion shortcuts, mst, and min-cut. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 202\u2013219 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch16","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"454_CR16","doi-asserted-by":"publisher","unstructured":"Haeupler, B., Izumi, T., Zuzic, G.: Low-congestion shortcuts without embedding. In: Giakkoupis, G. (ed.) Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, pp. 451\u2013460 (2016). https:\/\/doi.org\/10.1145\/2933057.2933112","DOI":"10.1145\/2933057.2933112"},{"key":"454_CR17","doi-asserted-by":"publisher","unstructured":"Haeupler, B., Izumi, T., Zuzic, G.: Near-optimal low-congestion shortcuts on bounded parameter graphs. In: Distributed Computing\u201430th International Symposium, DISC 2016. Lecture Notes in Computer Science, vol. 9888, pp. 158\u2013172 (2016). https:\/\/doi.org\/10.1007\/978-3-662-53426-7_12","DOI":"10.1007\/978-3-662-53426-7_12"},{"key":"454_CR18","doi-asserted-by":"publisher","unstructured":"Haeupler, B., Wajc, D., Zuzic, G.: Universally-optimal distributed algorithms for known topologies. In: STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1166\u20131179 (2021). https:\/\/doi.org\/10.1145\/3406325.3451081","DOI":"10.1145\/3406325.3451081"},{"key":"454_CR19","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Haeupler, B.: Low-congestion shortcuts for graphs excluding dense minors. In: PODC \u201921: ACM Symposium on Principles of Distributed Computing, 2021, pp. 213\u2013221 (2021). https:\/\/doi.org\/10.1145\/3465084.3467935","DOI":"10.1145\/3465084.3467935"},{"key":"454_CR20","doi-asserted-by":"publisher","unstructured":"Zuzic, G., Goranci, G., Ye, M., Haeupler, B., Sun, X.: Universally-optimal distributed shortest paths and transshipment via graph-based $$\\ell _1$$-oblivious routing. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2549\u20132579 (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.100 . SIAM","DOI":"10.1137\/1.9781611977073.100"},{"key":"454_CR21","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Zuzic, G.: Universally-optimal distributed exact min-cut. In: PODC \u201922: ACM Symposium on Principles of Distributed Computing, 2022, pp. 281\u2013291 (2022). https:\/\/doi.org\/10.1145\/3519270.3538429","DOI":"10.1145\/3519270.3538429"},{"key":"454_CR22","doi-asserted-by":"publisher","unstructured":"Haeupler, B., R\u00e4cke, H., Ghaffari, M.: Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. In: STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 1325\u20131338 (2022). https:\/\/doi.org\/10.1145\/3519935.3520026","DOI":"10.1145\/3519935.3520026"},{"key":"454_CR23","doi-asserted-by":"publisher","unstructured":"Augustine, J., Hinnenthal, K., Kuhn, F., Scheideler, C., Schneider, P.: Shortest paths in a hybrid network model. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pp. 1280\u20131299 (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.78","DOI":"10.1137\/1.9781611975994.78"},{"key":"454_CR24","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.jpdc.2016.05.009","volume":"96","author":"T Chen","year":"2016","unstructured":"Chen, T., Gao, X., Chen, G.: The features, hardware, and architectures of data center networks: a survey. J. Parallel Distrib. Comput. 96, 45\u201374 (2016). https:\/\/doi.org\/10.1016\/j.jpdc.2016.05.009","journal-title":"J. Parallel Distrib. Comput."},{"key":"454_CR25","doi-asserted-by":"publisher","unstructured":"Wang, G., Andersen, D.G., Kaminsky, M., Papagiannaki, K., Ng, T.S.E., Kozuch, M., Ryan, M.: C-through: Part-time optics in data centers. In: Proceedings of the ACM SIGCOMM 2010 Conference. SIGCOMM \u201910, pp. 327\u2013338 (2010). https:\/\/doi.org\/10.1145\/1851182.1851222","DOI":"10.1145\/1851182.1851222"},{"issue":"4","key":"454_CR26","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/j.icte.2017.08.002","volume":"4","author":"UN Kar","year":"2018","unstructured":"Kar, U.N., Sanyal, D.K.: An overview of device-to-device communication in cellular networks. ICT Express 4(4), 203\u2013208 (2018). https:\/\/doi.org\/10.1016\/j.icte.2017.08.002","journal-title":"ICT Express"},{"key":"454_CR27","doi-asserted-by":"publisher","unstructured":"Augustine, J., Ghaffari, M., Gmyr, R., Hinnenthal, K., Scheideler, C., Kuhn, F., Li, J.: Distributed computation in node-capacitated networks. In: The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, pp. 69\u201379 (2019). https:\/\/doi.org\/10.1145\/3323165.3323195","DOI":"10.1145\/3323165.3323195"},{"key":"454_CR28","doi-asserted-by":"publisher","unstructured":"Rozhon, V., Grunau, C., Haeupler, B., Zuzic, G., Li, J.: Undirected (1+$$\\epsilon $$)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms. In: STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 478\u2013487 (2022). https:\/\/doi.org\/10.1145\/3519935.3520074","DOI":"10.1145\/3519935.3520074"},{"key":"454_CR29","doi-asserted-by":"publisher","unstructured":"Censor-Hillel, K., Leitersdorf, D., Polosukhin, V.: On sparsity awareness in distributed computations. In: SPAA \u201921: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 151\u2013161 (2021). https:\/\/doi.org\/10.1145\/3409964.3461798","DOI":"10.1145\/3409964.3461798"},{"key":"454_CR30","doi-asserted-by":"publisher","unstructured":"Kuhn, F., Schneider, P.: Computing shortest paths and diameter in the hybrid network model. In: Proceedings of the 39th Symposium on Principles of Distributed Computing. PODC \u201920, pp. 109\u2013118 (2020). https:\/\/doi.org\/10.1145\/3382734.3405719","DOI":"10.1145\/3382734.3405719"},{"key":"454_CR31","doi-asserted-by":"publisher","unstructured":"Feldmann, M., Hinnenthal, K., Scheideler, C.: Fast hybrid network algorithms for shortest paths in sparse graphs. In: 24th International Conference on Principles of Distributed Systems, OPODIS 2020. LIPIcs, vol. 184, pp. 31\u201313116 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2020.31","DOI":"10.4230\/LIPIcs.OPODIS.2020.31"},{"key":"454_CR32","doi-asserted-by":"publisher","unstructured":"Censor-Hillel, K., Leitersdorf, D., Polosukhin, V.: Distance computations in the hybrid network model via oracle simulations. In: 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. LIPIcs, vol. 187, pp. 21\u201312119 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.21","DOI":"10.4230\/LIPIcs.STACS.2021.21"},{"key":"454_CR33","doi-asserted-by":"publisher","unstructured":"G\u00f6tte, T., Hinnenthal, K., Scheideler, C., Werthmann, J.: Time-optimal construction of overlay networks. In: PODC \u201921: ACM Symposium on Principles of Distributed Computing, pp. 457\u2013468 (2021). https:\/\/doi.org\/10.1145\/3465084.3467932","DOI":"10.1145\/3465084.3467932"},{"key":"454_CR34","doi-asserted-by":"publisher","unstructured":"Kuhn, F., Schneider, P.: Routing schemes and distance oracles in the hybrid model. In: 36th International Symposium on Distributed Computing, DISC 2022. LIPIcs, vol. 246, pp. 28\u201312822 (2022). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2022.28","DOI":"10.4230\/LIPIcs.DISC.2022.28"},{"key":"454_CR35","doi-asserted-by":"publisher","unstructured":"Coy, S., Czumaj, A., Feldmann, M., Hinnenthal, K., Kuhn, F., Scheideler, C., Schneider, P., Struijs, M.: Near-shortest path routing in hybrid communication networks. In: 25th International Conference on Principles of Distributed Systems, OPODIS 2021. LIPIcs, vol. 217, pp. 11\u201311123 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2021.11","DOI":"10.4230\/LIPIcs.OPODIS.2021.11"},{"key":"454_CR36","doi-asserted-by":"publisher","unstructured":"Anagnostides, I., Gouleakis, T.: Deterministic distributed algorithms and lower bounds in the hybrid model. In: 35th International Symposium on Distributed Computing, DISC 2021. LIPIcs, vol. 209, pp. 5\u20131519 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.5","DOI":"10.4230\/LIPIcs.DISC.2021.5"},{"key":"454_CR37","doi-asserted-by":"publisher","unstructured":"Peng, R., Spielman, D.A.: An efficient parallel solver for SDD linear systems. In: Symposium on Theory of Computing, STOC 2014, pp. 333\u2013342 (2014). https:\/\/doi.org\/10.1145\/2591796.2591832","DOI":"10.1145\/2591796.2591832"},{"issue":"3","key":"454_CR38","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00224-013-9444-5","volume":"55","author":"GE Blelloch","year":"2014","unstructured":"Blelloch, G.E., Gupta, A., Koutis, I., Miller, G.L., Peng, R., Tangwongsan, K.: Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs. Theory Comput. Syst. 55(3), 521\u2013554 (2014). https:\/\/doi.org\/10.1007\/s00224-013-9444-5","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"454_CR39","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."},{"key":"454_CR40","doi-asserted-by":"publisher","unstructured":"Lotker, Z., Pavlov, E., Patt-Shamir, B., Peleg, D.: MST construction in $${O}(\\log \\log n)$$ communication rounds. In: SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003, pp. 94\u2013100 (2003). https:\/\/doi.org\/10.1145\/777412.777428","DOI":"10.1145\/777412.777428"},{"key":"454_CR41","doi-asserted-by":"publisher","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: ACM Symposium on Principles of Distributed Computing, PODC \u201914, pp. 367\u2013376 (2014). https:\/\/doi.org\/10.1145\/2611462.2611493","DOI":"10.1145\/2611462.2611493"},{"key":"454_CR42","doi-asserted-by":"publisher","unstructured":"Forster, S., Vos, T.: The Laplacian paradigm in the broadcast congested clique. In: PODC \u201922: ACM Symposium on Principles of Distributed Computing, Salerno, 2022, pp. 335\u2013344 (2022). https:\/\/doi.org\/10.1145\/3519270.3538436","DOI":"10.1145\/3519270.3538436"},{"key":"454_CR43","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. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"454_CR44","doi-asserted-by":"publisher","unstructured":"Schmid, S., Suomela, J.: Exploiting locality in distributed SDN control. HotSDN 2013\u2014Proceedings of the 2013 ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, pp. 121\u2013126 (2013). https:\/\/doi.org\/10.1145\/2491185.2491198","DOI":"10.1145\/2491185.2491198"},{"key":"454_CR45","doi-asserted-by":"publisher","unstructured":"Ghaffari, M.: Near-Optimal Scheduling of Distributed Algorithms. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 3\u201312 (2015). https:\/\/doi.org\/10.1145\/2767386.2767417","DOI":"10.1145\/2767386.2767417"},{"issue":"5","key":"454_CR46","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0020-0190(99)00064-2","volume":"70","author":"\u00d6 Johansson","year":"1999","unstructured":"Johansson, \u00d6.: Simple distributed $$\\delta + 1$$-coloring of graphs. Inf. Process. Lett. 70(5), 229\u2013232 (1999)","journal-title":"Inf. Process. Lett."},{"key":"454_CR47","doi-asserted-by":"publisher","unstructured":"Haeupler, B., Wajc, D., Zuzic, G.: Network coding gaps for completion times of multiple unicasts. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 494\u2013505 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00053 . IEEE","DOI":"10.1109\/FOCS46700.2020.00053"},{"key":"454_CR48","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Karrenbauer, A., Kuhn, F., Lenzen, C., Patt-Shamir, B.: Near-optimal distributed maximum flow: extended abstract. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pp. 81\u201390 (2015). https:\/\/doi.org\/10.1145\/2767386.2767440","DOI":"10.1145\/2767386.2767440"},{"issue":"1","key":"454_CR49","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N Alon","year":"1995","unstructured":"Alon, N., Karp, R.M., Peleg, D., West, D.: A graph-theoretic game and its application to the $$k$$-server problem. SIAM J. Comput. 24(1), 78\u2013100 (1995). https:\/\/doi.org\/10.1137\/S0097539792224474","journal-title":"SIAM J. Comput."},{"key":"454_CR50","doi-asserted-by":"publisher","unstructured":"Koutis, I., Miller, G.L., Peng, R.: Approaching optimality for solving sdd linear systems. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 235\u2013244 (2010). https:\/\/doi.org\/10.1109\/FOCS.2010.29","DOI":"10.1109\/FOCS.2010.29"},{"key":"454_CR51","doi-asserted-by":"publisher","unstructured":"Kyng, R., Lee, Y.T., Peng, R., Sachdeva, S., Spielman, D.A.: Sparsified cholesky and multigrid solvers for connection laplacians. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. STOC \u201916, pp. 842\u2013850. Association for Computing Machinery, New York, NY, USA (2016). https:\/\/doi.org\/10.1145\/2897518.2897640","DOI":"10.1145\/2897518.2897640"},{"key":"454_CR52","doi-asserted-by":"publisher","unstructured":"Durfee, D., Gao, Y., Goranci, G., Peng, R.: Fully dynamic spectral vertex sparsifiers and applications. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 914\u2013925 (2019). https:\/\/doi.org\/10.1145\/3313276.3316379","DOI":"10.1145\/3313276.3316379"},{"key":"454_CR53","doi-asserted-by":"publisher","unstructured":"Li, H., Schild, A.: Spectral subspace sparsification. In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pp. 385\u2013396 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00044","DOI":"10.1109\/FOCS.2018.00044"},{"key":"454_CR54","doi-asserted-by":"publisher","unstructured":"Schild, A., Rao, S., Srivastava, N.: Localization of electrical flows. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. SODA \u201918, pp. 1577\u20131584. Society for Industrial and Applied Mathematics, USA (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.103","DOI":"10.1137\/1.9781611975031.103"},{"key":"454_CR55","doi-asserted-by":"publisher","unstructured":"Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. In: Dwork, C. (ed.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 563\u2013568 (2008). https:\/\/doi.org\/10.1145\/1374376.1374456","DOI":"10.1145\/1374376.1374456"},{"key":"454_CR56","doi-asserted-by":"publisher","DOI":"10.1561\/0400000054","author":"N Vishnoi","year":"2012","unstructured":"Vishnoi, N.: Lx=b. Laplacian solvers and their algorithmic applications. Found. Trends Theor. Comput. Sci. (2012). https:\/\/doi.org\/10.1561\/0400000054","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"454_CR57","doi-asserted-by":"publisher","unstructured":"Koutis, I.: Simple parallel and distributed algorithms for spectral graph sparsification. In: 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201914, pp. 61\u201366 (2014). https:\/\/doi.org\/10.1145\/2612669.2612676","DOI":"10.1145\/2612669.2612676"},{"issue":"4","key":"454_CR58","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). https:\/\/doi.org\/10.1002\/rsa.20130","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"454_CR59","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/1147954.1147955","volume":"53","author":"P Indyk","year":"2006","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM 53(3), 307\u2013323 (2006). https:\/\/doi.org\/10.1145\/1147954.1147955","journal-title":"J. ACM"},{"issue":"4","key":"454_CR60","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D Achlioptas","year":"2003","unstructured":"Achlioptas, D.: Database-friendly random projections: Johnson\u2013lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671\u2013687 (2003). https:\/\/doi.org\/10.1016\/S0022-0000(03)00025-4","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00454-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-023-00454-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00454-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T09:06:54Z","timestamp":1697447214000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-023-00454-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,31]]},"references-count":60,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["454"],"URL":"https:\/\/doi.org\/10.1007\/s00446-023-00454-0","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2481782\/v1","asserted-by":"object"}]},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,31]]},"assertion":[{"value":"15 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}