[{"file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"626551c14de5d4091573200ed0535752","file_id":"11345","success":1,"date_updated":"2022-05-02T07:53:00Z","file_size":790396,"creator":"dernst","date_created":"2022-05-02T07:53:00Z","file_name":"2022_LIPICs_Nikabadi.pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772198"]},"publication_status":"published","volume":217,"ec_funded":1,"oa_version":"Published Version","abstract":[{"text":"Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems closely related to subgraph detection, mainly focusing on induced subgraph detection. The main line of this work presents lower bounds and parameterized algorithms w.r.t structural parameters of the input graph:\r\n- On general graphs, we give unconditional lower bounds for induced detection of cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions from centralized parameterized complexity, we prove lower bounds in CONGEST for detecting patterns with a 4-clique, and for induced path detection conditional on the hardness of triangle detection in the congested clique.\r\n- On graphs of bounded degeneracy, we show that induced paths can be detected fast in CONGEST using techniques from parameterized algorithms, while detecting cycles and patterns of treewidth 2 is hard.\r\n- On graphs of bounded vertex cover number, we show that induced subgraph detection is easy in CONGEST for any pattern graph. More specifically, we adapt a centralized parameterized algorithm for a more general maximum common induced subgraph detection problem to the distributed setting. In addition to these induced subgraph detection results, we study various related problems in the CONGEST and congested clique models, including for multicolored versions of subgraph-detection-like problems.","lang":"eng"}],"month":"02","intvolume":" 217","alternative_title":["LIPIcs"],"scopus_import":"1","ddc":["510"],"date_updated":"2022-05-02T07:56:35Z","department":[{"_id":"DaAl"}],"file_date_updated":"2022-05-02T07:53:00Z","_id":"11183","status":"public","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"end_date":"2021-12-15","location":"Strasbourg, France","start_date":"2021-12-13","name":"OPODIS"},"day":"01","publication":"25th International Conference on Principles of Distributed Systems","has_accepted_license":"1","year":"2022","doi":"10.4230/LIPIcs.OPODIS.2021.15","date_published":"2022-02-01T00:00:00Z","date_created":"2022-04-17T22:01:47Z","acknowledgement":"Amir Nikabadi: Supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). Janne H. Korhonen: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).\r\nWe thank François Le Gall and Masayuki Miyamoto for sharing their work on lower bounds for induced subgraph detection [36].","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters.” 25th International Conference on Principles of Distributed Systems, edited by Quentin Bramas et al., vol. 217, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.OPODIS.2021.15.","short":"A. Nikabadi, J. Korhonen, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ieee":"A. Nikabadi and J. Korhonen, “Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters,” in 25th International Conference on Principles of Distributed Systems, Strasbourg, France, 2022, vol. 217.","apa":"Nikabadi, A., & Korhonen, J. (2022). Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters. In Q. Bramas, V. Gramoli, & A. Milani (Eds.), 25th International Conference on Principles of Distributed Systems (Vol. 217). Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.15","ama":"Nikabadi A, Korhonen J. Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters. In: Bramas Q, Gramoli V, Milani A, eds. 25th International Conference on Principles of Distributed Systems. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.OPODIS.2021.15","chicago":"Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters.” In 25th International Conference on Principles of Distributed Systems, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.15.","ista":"Nikabadi A, Korhonen J. 2022. Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters. 25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 15."},"title":"Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters","editor":[{"full_name":"Bramas, Quentin","last_name":"Bramas","first_name":"Quentin"},{"full_name":"Gramoli, Vincent","last_name":"Gramoli","first_name":"Vincent"},{"last_name":"Milani","full_name":"Milani, Alessia","first_name":"Alessia"}],"author":[{"first_name":"Amir","last_name":"Nikabadi","full_name":"Nikabadi, Amir"},{"last_name":"Korhonen","full_name":"Korhonen, Janne","first_name":"Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425"}],"article_processing_charge":"No","article_number":"15","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}]},{"status":"public","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"DISC: Distributed Computing ","start_date":"2021-10-04","end_date":"2021-10-08","location":"Freiburg, Germany"},"_id":"10219","file_date_updated":"2021-11-12T08:27:42Z","department":[{"_id":"DaAl"}],"ddc":["000"],"date_updated":"2021-11-12T09:37:18Z","month":"10","intvolume":" 209","alternative_title":["LIPIcs"],"scopus_import":"1","oa_version":"Published Version","abstract":[{"lang":"eng","text":"We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n)."}],"volume":209,"ec_funded":1,"file":[{"checksum":"c43188dc2070bbd2bf5fd6fdaf9ce36d","file_id":"10275","success":1,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2021-11-12T08:27:42Z","file_name":"2021_LIPIcsDISC_Korhonen.pdf","date_updated":"2021-11-12T08:27:42Z","file_size":474242,"creator":"cchlebak"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"publication_status":"published","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"article_number":"58","title":"Brief announcement: Sinkless orientation is hard also in the supported LOCAL model","author":[{"full_name":"Korhonen, Janne","last_name":"Korhonen","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne"},{"first_name":"Ami","full_name":"Paz, Ami","last_name":"Paz"},{"full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"first_name":"Jukka","last_name":"Suomela","full_name":"Suomela, Jukka"}],"external_id":{"arxiv":["2108.02655"]},"article_processing_charge":"No","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"ista":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. 2021. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 58.","chicago":"Korhonen, Janne, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” In 35th International Symposium on Distributed Computing, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.58.","ama":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In: 35th International Symposium on Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.58","apa":"Korhonen, J., Paz, A., Rybicki, J., Schmid, S., & Suomela, J. (2021). Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In 35th International Symposium on Distributed Computing (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.58","short":"J. Korhonen, A. Paz, J. Rybicki, S. Schmid, J. Suomela, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","ieee":"J. Korhonen, A. Paz, J. Rybicki, S. Schmid, and J. Suomela, “Brief announcement: Sinkless orientation is hard also in the supported LOCAL model,” in 35th International Symposium on Distributed Computing, Freiburg, Germany, 2021, vol. 209.","mla":"Korhonen, Janne, et al. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” 35th International Symposium on Distributed Computing, vol. 209, 58, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.DISC.2021.58."},"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","oa":1,"acknowledgement":"Janne H. Korhonen: Project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Ami Paz: We acknowledge the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Stefan Schmid: Research supported by the Austrian Science Fund (FWF) project ADVISE, I 4800-N, 2020-2023.\r\n","doi":"10.4230/LIPIcs.DISC.2021.58","date_published":"2021-10-04T00:00:00Z","date_created":"2021-11-07T23:01:24Z","day":"04","publication":"35th International Symposium on Distributed Computing","has_accepted_license":"1","year":"2021"},{"conference":{"end_date":"2021-12-14","location":"Virtual, Online","start_date":"2021-12-06","name":"NeurIPS: Neural Information Processing Systems"},"type":"conference","status":"public","_id":"11464","department":[{"_id":"DaAl"}],"date_updated":"2022-06-27T06:54:31Z","main_file_link":[{"url":"https://proceedings.neurips.cc/paper/2021/file/3b92d18aa7a6176dd37d372bc2f1eb71-Paper.pdf","open_access":"1"}],"scopus_import":"1","intvolume":" 34","month":"12","abstract":[{"text":"We consider a standard distributed optimisation setting where N machines, each holding a d-dimensional function\r\nfi, aim to jointly minimise the sum of the functions ∑Ni=1fi(x). This problem arises naturally in large-scale distributed optimisation, where a standard solution is to apply variants of (stochastic) gradient descent. We focus on the communication complexity of this problem: our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the N machines to solve this problem under point-to-point communication, within a given error-tolerance. Specifically, we show that Ω(Ndlogd/Nε) total bits need to be communicated between the machines to find an additive ϵ-approximation to the minimum of ∑Ni=1fi(x). The result holds for both deterministic and randomised algorithms, and, importantly, requires no assumptions on the algorithm structure. The lower bound is tight under certain restrictions on parameter values, and is matched within constant factors for quadratic objectives by a new variant of quantised gradient descent, which we describe and analyse. Our results bring over tools from communication complexity to distributed optimisation, which has potential for further applications.","lang":"eng"}],"oa_version":"Published Version","ec_funded":1,"volume":34,"publication_status":"published","publication_identifier":{"isbn":["9781713845393"],"issn":["1049-5258"]},"language":[{"iso":"eng"}],"project":[{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning"}],"article_processing_charge":"No","external_id":{"arxiv":["2010.08222"]},"author":[{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"},{"last_name":"Korhonen","full_name":"Korhonen, Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne"}],"title":"Towards tight communication lower bounds for distributed optimisation","citation":{"chicago":"Alistarh, Dan-Adrian, and Janne Korhonen. “Towards Tight Communication Lower Bounds for Distributed Optimisation.” In 35th Conference on Neural Information Processing Systems, 34:7254–66. Curran Associates, 2021.","ista":"Alistarh D-A, Korhonen J. 2021. Towards tight communication lower bounds for distributed optimisation. 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems vol. 34, 7254–7266.","mla":"Alistarh, Dan-Adrian, and Janne Korhonen. “Towards Tight Communication Lower Bounds for Distributed Optimisation.” 35th Conference on Neural Information Processing Systems, vol. 34, Curran Associates, 2021, pp. 7254–66.","ieee":"D.-A. Alistarh and J. Korhonen, “Towards tight communication lower bounds for distributed optimisation,” in 35th Conference on Neural Information Processing Systems, Virtual, Online, 2021, vol. 34, pp. 7254–7266.","short":"D.-A. Alistarh, J. Korhonen, in:, 35th Conference on Neural Information Processing Systems, Curran Associates, 2021, pp. 7254–7266.","ama":"Alistarh D-A, Korhonen J. Towards tight communication lower bounds for distributed optimisation. In: 35th Conference on Neural Information Processing Systems. Vol 34. Curran Associates; 2021:7254-7266.","apa":"Alistarh, D.-A., & Korhonen, J. (2021). Towards tight communication lower bounds for distributed optimisation. In 35th Conference on Neural Information Processing Systems (Vol. 34, pp. 7254–7266). Virtual, Online: Curran Associates."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"quality_controlled":"1","publisher":"Curran Associates","acknowledgement":"We thank the NeurIPS reviewers for insightful comments that helped us improve the positioning of our results, as well as for pointing out the subsampling approach for complementing the randomised lower bound. We also thank Foivos Alimisis and Peter Davies for useful discussions. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).","page":"7254-7266","date_created":"2022-06-26T22:01:35Z","date_published":"2021-12-06T00:00:00Z","year":"2021","publication":"35th Conference on Neural Information Processing Systems","day":"06"},{"publication_identifier":{"isbn":["9781450380720"]},"publication_status":"published","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"extended_version","id":"10855","status":"public"}]},"ec_funded":1,"abstract":[{"text":"Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner?\r\nTo address this question, we define the batch dynamic CONGEST model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labelled graph under batch changes. We investigate, when a batch of alpha edge label changes arrive, - how much time as a function of alpha we need to update an existing solution, and - how much information the nodes have to keep in local memory between batches in order to update the solution quickly.\r\nOur work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. The diverse time complexity of our model spans from constant time, through time polynomial in alpha, and to alpha time, which we show to be enough for any task.","lang":"eng"}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/2005.07637","open_access":"1"}],"month":"05","date_updated":"2023-09-26T10:40:55Z","department":[{"_id":"DaAl"}],"_id":"10854","type":"conference","conference":{"name":"SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems","end_date":"2021-06-18","location":"Virtual, Online","start_date":"2021-06-14"},"status":"public","year":"2021","day":"01","publication":"Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems","page":"71-72","date_published":"2021-05-01T00:00:00Z","doi":"10.1145/3410220.3453923","date_created":"2022-03-18T08:48:41Z","acknowledgement":"We thank Jukka Suomela for discussions. We also thank our shepherd Mohammad Hajiesmaili and the reviewers for their time and suggestions on how to improve the paper. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie grant agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.","quality_controlled":"1","publisher":"Association for Computing Machinery","oa":1,"citation":{"mla":"Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication Networks.” Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery, 2021, pp. 71–72, doi:10.1145/3410220.3453923.","short":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, in:, Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery, 2021, pp. 71–72.","ieee":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic distributed algorithms for communication networks,” in Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Virtual, Online, 2021, pp. 71–72.","apa":"Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., & Schmid, S. (2021). Input-dynamic distributed algorithms for communication networks. In Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems (pp. 71–72). Virtual, Online: Association for Computing Machinery. https://doi.org/10.1145/3410220.3453923","ama":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed algorithms for communication networks. In: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. Association for Computing Machinery; 2021:71-72. doi:10.1145/3410220.3453923","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” In Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, 71–72. Association for Computing Machinery, 2021. https://doi.org/10.1145/3410220.3453923.","ista":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic distributed algorithms for communication networks. Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems, 71–72."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Foerster","full_name":"Foerster, Klaus-Tycho","first_name":"Klaus-Tycho"},{"last_name":"Korhonen","full_name":"Korhonen, Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne"},{"first_name":"Ami","full_name":"Paz, Ami","last_name":"Paz"},{"last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"}],"article_processing_charge":"No","external_id":{"arxiv":["2005.07637"]},"title":"Input-dynamic distributed algorithms for communication networks","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"call_identifier":"H2020","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","grant_number":"840605","name":"Coordination in constrained and natural distributed systems"}]},{"date_updated":"2023-09-26T10:40:55Z","department":[{"_id":"DaAl"}],"_id":"10855","article_type":"original","type":"journal_article","keyword":["Computer Networks and Communications","Hardware and Architecture","Safety","Risk","Reliability and Quality","Computer Science (miscellaneous)"],"status":"public","publication_status":"published","publication_identifier":{"issn":["2476-1249"]},"language":[{"iso":"eng"}],"ec_funded":1,"volume":5,"issue":"1","related_material":{"record":[{"relation":"shorter_version","id":"10854","status":"public"}]},"abstract":[{"lang":"eng","text":"Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic \\congest model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of α edge label changes arrive, \\beginitemize \\item how much time as a function of α we need to update an existing solution, and \\item how much information the nodes have to keep in local memory between batches in order to update the solution quickly. \\enditemize Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques."}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2005.07637"}],"scopus_import":"1","intvolume":" 5","month":"03","citation":{"ieee":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic distributed algorithms for communication networks,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 5, no. 1. Association for Computing Machinery, pp. 1–33, 2021.","short":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, Proceedings of the ACM on Measurement and Analysis of Computing Systems 5 (2021) 1–33.","apa":"Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., & Schmid, S. (2021). Input-dynamic distributed algorithms for communication networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems. Association for Computing Machinery. https://doi.org/10.1145/3447384","ama":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed algorithms for communication networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2021;5(1):1-33. doi:10.1145/3447384","mla":"Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication Networks.” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 5, no. 1, Association for Computing Machinery, 2021, pp. 1–33, doi:10.1145/3447384.","ista":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic distributed algorithms for communication networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 5(1), 1–33.","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” Proceedings of the ACM on Measurement and Analysis of Computing Systems. Association for Computing Machinery, 2021. https://doi.org/10.1145/3447384."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","external_id":{"arxiv":["2005.07637"]},"author":[{"last_name":"Foerster","full_name":"Foerster, Klaus-Tycho","first_name":"Klaus-Tycho"},{"id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne","full_name":"Korhonen, Janne","last_name":"Korhonen"},{"full_name":"Paz, Ami","last_name":"Paz","first_name":"Ami"},{"last_name":"Rybicki","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"}],"title":"Input-dynamic distributed algorithms for communication networks","project":[{"_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"840605","name":"Coordination in constrained and natural distributed systems"},{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223"}],"year":"2021","publication":"Proceedings of the ACM on Measurement and Analysis of Computing Systems","day":"01","page":"1-33","date_created":"2022-03-18T09:10:27Z","date_published":"2021-03-01T00:00:00Z","doi":"10.1145/3447384","acknowledgement":"We thank Jukka Suomela for discussions. We also thank our shepherd Mohammad Hajiesmaili\r\nand the reviewers for their time and suggestions on how to improve the paper. This project\r\nhas received funding from the European Research Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research and innovation programme under the Marie\r\nSk lodowska–Curie grant agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.","oa":1,"quality_controlled":"1","publisher":"Association for Computing Machinery"},{"article_processing_charge":"Yes (via OA deal)","external_id":{"isi":["000556444600001"],"arxiv":["1903.05956"]},"author":[{"full_name":"Censor-Hillel, Keren","last_name":"Censor-Hillel","first_name":"Keren"},{"full_name":"Dory, Michal","last_name":"Dory","first_name":"Michal"},{"last_name":"Korhonen","full_name":"Korhonen, Janne","first_name":"Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425"},{"first_name":"Dean","last_name":"Leitersdorf","full_name":"Leitersdorf, Dean"}],"title":"Fast approximate shortest paths in the congested clique","citation":{"ieee":"K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate shortest paths in the congested clique,” Distributed Computing, vol. 34. Springer Nature, pp. 463–487, 2021.","short":"K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, Distributed Computing 34 (2021) 463–487.","ama":"Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest paths in the congested clique. Distributed Computing. 2021;34:463-487. doi:10.1007/s00446-020-00380-5","apa":"Censor-Hillel, K., Dory, M., Korhonen, J., & Leitersdorf, D. (2021). Fast approximate shortest paths in the congested clique. Distributed Computing. Springer Nature. https://doi.org/10.1007/s00446-020-00380-5","mla":"Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested Clique.” Distributed Computing, vol. 34, Springer Nature, 2021, pp. 463–87, doi:10.1007/s00446-020-00380-5.","ista":"Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2021. Fast approximate shortest paths in the congested clique. Distributed Computing. 34, 463–487.","chicago":"Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf. “Fast Approximate Shortest Paths in the Congested Clique.” Distributed Computing. Springer Nature, 2021. https://doi.org/10.1007/s00446-020-00380-5."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"page":"463-487","date_created":"2020-06-07T22:00:54Z","date_published":"2021-12-01T00:00:00Z","doi":"10.1007/s00446-020-00380-5","year":"2021","isi":1,"publication":"Distributed Computing","day":"01","oa":1,"publisher":"Springer Nature","quality_controlled":"1","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). We thank Mohsen Ghaffari, Michael Elkin and Merav Parter for fruitful discussions. This project has received funding from the European Union’s Horizon 2020 Research And Innovation Program under Grant Agreement No. 755839.","department":[{"_id":"DaAl"}],"date_updated":"2024-03-07T14:43:39Z","article_type":"original","type":"journal_article","status":"public","_id":"7939","volume":34,"related_material":{"record":[{"relation":"earlier_version","id":"6933","status":"public"}]},"publication_status":"published","publication_identifier":{"issn":["0178-2770"],"eissn":["1432-0452"]},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00446-020-00380-5"}],"scopus_import":"1","intvolume":" 34","month":"12","abstract":[{"lang":"eng","text":"We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include:\r\n A (2+ϵ)-approximation for all-pairs shortest paths in O(log2n/ϵ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.\r\n A (1+ϵ)-approximation for multi-source shortest paths from O(n−−√) sources in O(log2n/ϵ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.\r\n\r\nOur main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in O~(n1/6) rounds. "}],"oa_version":"Published Version"},{"acknowledgement":"We thank Marco Mondelli for discussions related to LDPC decoding, and Giorgi Nadiradze for discussions on analysis of relaxed schedulers. This project has received funding from the European Research Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).","oa":1,"publisher":"Curran Associates","quality_controlled":"1","year":"2020","publication":"Advances in Neural Information Processing Systems","day":"06","page":"22361-22372","date_created":"2021-07-04T22:01:26Z","date_published":"2020-12-06T00:00:00Z","project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning"}],"citation":{"ama":"Aksenov V, Alistarh D-A, Korhonen J. Scalable belief propagation via relaxed scheduling. In: Advances in Neural Information Processing Systems. Vol 33. Curran Associates; 2020:22361-22372.","apa":"Aksenov, V., Alistarh, D.-A., & Korhonen, J. (2020). Scalable belief propagation via relaxed scheduling. In Advances in Neural Information Processing Systems (Vol. 33, pp. 22361–22372). Vancouver, Canada: Curran Associates.","short":"V. Aksenov, D.-A. Alistarh, J. Korhonen, in:, Advances in Neural Information Processing Systems, Curran Associates, 2020, pp. 22361–22372.","ieee":"V. Aksenov, D.-A. Alistarh, and J. Korhonen, “Scalable belief propagation via relaxed scheduling,” in Advances in Neural Information Processing Systems, Vancouver, Canada, 2020, vol. 33, pp. 22361–22372.","mla":"Aksenov, Vitaly, et al. “Scalable Belief Propagation via Relaxed Scheduling.” Advances in Neural Information Processing Systems, vol. 33, Curran Associates, 2020, pp. 22361–72.","ista":"Aksenov V, Alistarh D-A, Korhonen J. 2020. Scalable belief propagation via relaxed scheduling. Advances in Neural Information Processing Systems. NeurIPS: Conference on Neural Information Processing Systems vol. 33, 22361–22372.","chicago":"Aksenov, Vitaly, Dan-Adrian Alistarh, and Janne Korhonen. “Scalable Belief Propagation via Relaxed Scheduling.” In Advances in Neural Information Processing Systems, 33:22361–72. Curran Associates, 2020."},"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","article_processing_charge":"No","external_id":{"arxiv":["2002.11505"]},"author":[{"first_name":"Vitaly","last_name":"Aksenov","full_name":"Aksenov, Vitaly"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","last_name":"Korhonen","full_name":"Korhonen, Janne"}],"title":"Scalable belief propagation via relaxed scheduling","abstract":[{"lang":"eng","text":"The ability to leverage large-scale hardware parallelism has been one of the key enablers of the accelerated recent progress in machine learning. Consequently, there has been considerable effort invested into developing efficient parallel variants of classic machine learning algorithms. However, despite the wealth of knowledge on parallelization, some classic machine learning algorithms often prove hard to parallelize efficiently while maintaining convergence. In this paper, we focus on efficient parallel algorithms for the key machine learning task of inference on graphical models, in particular on the fundamental belief propagation algorithm. We address the challenge of efficiently parallelizing this classic paradigm by showing how to leverage scalable relaxed schedulers in this context. We present an extensive empirical study, showing that our approach outperforms previous parallel belief propagation implementations both in terms of scalability and in terms of wall-clock convergence time, on a range of practical applications."}],"oa_version":"Published Version","main_file_link":[{"open_access":"1","url":"https://proceedings.neurips.cc/paper/2020/hash/fdb2c3bab9d0701c4a050a4d8d782c7f-Abstract.html"}],"scopus_import":"1","intvolume":" 33","month":"12","publication_status":"published","publication_identifier":{"issn":["10495258"],"isbn":["9781713829546"]},"language":[{"iso":"eng"}],"ec_funded":1,"volume":33,"_id":"9631","conference":{"start_date":"2020-12-06","end_date":"2020-12-12","location":"Vancouver, Canada","name":"NeurIPS: Conference on Neural Information Processing Systems"},"type":"conference","status":"public","date_updated":"2023-02-23T14:03:03Z","department":[{"_id":"DaAl"}]},{"volume":32,"issue":"6","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0178-2770","1432-0452"]},"publication_status":"published","month":"12","intvolume":" 32","main_file_link":[{"url":"https://arxiv.org/abs/1503.04963","open_access":"1"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an O(n1−2/ω) round matrix multiplication algorithm, where ω<2.3728639 is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include:\r\n\r\n1. triangle and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) algorithm of Dolev et al. [DISC 2012],\r\n2. a (1+o(1))-approximation of all-pairs shortest paths in O(n0.158) rounds, improving upon the O~(n1/2)-round (2+o(1))-approximation algorithm given by Nanongkai [STOC 2014], and\r\n 3. computing the girth in O(n0.158) rounds, which is the first non-trivial solution in this model.\r\n \r\nIn addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles."}],"extern":"1","date_updated":"2021-01-12T08:12:05Z","status":"public","article_type":"original","type":"journal_article","_id":"7150","date_published":"2019-12-01T00:00:00Z","doi":"10.1007/s00446-016-0270-2","date_created":"2019-12-05T09:49:49Z","page":"461-478","day":"01","publication":"Distributed Computing","year":"2019","quality_controlled":"1","publisher":"Springer Nature","oa":1,"title":"Algebraic methods in the congested clique","author":[{"full_name":"Censor-Hillel, Keren","last_name":"Censor-Hillel","first_name":"Keren"},{"first_name":"Petteri","full_name":"Kaski, Petteri","last_name":"Kaski"},{"id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne","last_name":"Korhonen","full_name":"Korhonen, Janne"},{"first_name":"Christoph","last_name":"Lenzen","full_name":"Lenzen, Christoph"},{"first_name":"Ami","full_name":"Paz, Ami","last_name":"Paz"},{"first_name":"Jukka","full_name":"Suomela, Jukka","last_name":"Suomela"}],"article_processing_charge":"No","external_id":{"arxiv":["1503.04963"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, J. Suomela, Distributed Computing 32 (2019) 461–478.","ieee":"K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, and J. Suomela, “Algebraic methods in the congested clique,” Distributed Computing, vol. 32, no. 6. Springer Nature, pp. 461–478, 2019.","apa":"Censor-Hillel, K., Kaski, P., Korhonen, J., Lenzen, C., Paz, A., & Suomela, J. (2019). Algebraic methods in the congested clique. Distributed Computing. Springer Nature. https://doi.org/10.1007/s00446-016-0270-2","ama":"Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. Algebraic methods in the congested clique. Distributed Computing. 2019;32(6):461-478. doi:10.1007/s00446-016-0270-2","mla":"Censor-Hillel, Keren, et al. “Algebraic Methods in the Congested Clique.” Distributed Computing, vol. 32, no. 6, Springer Nature, 2019, pp. 461–78, doi:10.1007/s00446-016-0270-2.","ista":"Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. 2019. Algebraic methods in the congested clique. Distributed Computing. 32(6), 461–478.","chicago":"Censor-Hillel, Keren, Petteri Kaski, Janne Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. “Algebraic Methods in the Congested Clique.” Distributed Computing. Springer Nature, 2019. https://doi.org/10.1007/s00446-016-0270-2."}},{"oa":1,"quality_controlled":"1","publisher":"ACM","year":"2019","isi":1,"publication":"Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing","day":"01","page":"259-261","date_created":"2019-10-08T12:57:14Z","doi":"10.1145/3293611.3331581","date_published":"2019-08-01T00:00:00Z","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"citation":{"ista":"Foerster K-T, Korhonen J, Rybicki J, Schmid S. 2019. Does preprocessing help under congestion? Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 259–261.","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Joel Rybicki, and Stefan Schmid. “Does Preprocessing Help under Congestion?” In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 259–61. ACM, 2019. https://doi.org/10.1145/3293611.3331581.","ieee":"K.-T. Foerster, J. Korhonen, J. Rybicki, and S. Schmid, “Does preprocessing help under congestion?,” in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, Toronto, ON, Canada, 2019, pp. 259–261.","short":"K.-T. Foerster, J. Korhonen, J. Rybicki, S. Schmid, in:, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019, pp. 259–261.","apa":"Foerster, K.-T., Korhonen, J., Rybicki, J., & Schmid, S. (2019). Does preprocessing help under congestion? In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (pp. 259–261). Toronto, ON, Canada: ACM. https://doi.org/10.1145/3293611.3331581","ama":"Foerster K-T, Korhonen J, Rybicki J, Schmid S. Does preprocessing help under congestion? In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. ACM; 2019:259-261. doi:10.1145/3293611.3331581","mla":"Foerster, Klaus-Tycho, et al. “Does Preprocessing Help under Congestion?” Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019, pp. 259–61, doi:10.1145/3293611.3331581."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","external_id":{"arxiv":["1905.03012"],"isi":["000570442000037"]},"author":[{"last_name":"Foerster","full_name":"Foerster, Klaus-Tycho","first_name":"Klaus-Tycho"},{"last_name":"Korhonen","full_name":"Korhonen, Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne"},{"first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel"},{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"}],"title":"Does preprocessing help under congestion?","abstract":[{"text":"This paper investigates the power of preprocessing in the CONGEST model. Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to study the application of distributed algorithms in Software-Defined Networks (SDNs). In this paper, we show that a large class of lower bounds in the CONGEST model still hold in the SUPPORTED model, highlighting the robustness of these bounds. This also raises the question how much does\r\npreprocessing help in the CONGEST model.","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1905.03012","open_access":"1"}],"scopus_import":"1","month":"08","publication_status":"published","publication_identifier":{"isbn":["9781450362177"]},"language":[{"iso":"eng"}],"ec_funded":1,"_id":"6935","conference":{"name":"PODC: Symposium on Principles of Distributed Computing","start_date":"2019-07-29","end_date":"2019-08-02","location":"Toronto, ON, Canada"},"type":"conference","status":"public","date_updated":"2023-09-08T11:37:22Z","department":[{"_id":"DaAl"}]},{"_id":"6933","status":"public","type":"conference","conference":{"name":"PODC: Symposium on Principles of Distributed Computing","location":"Toronto, ON, Canada","end_date":"2019-08-02","start_date":"2019-07-29"},"date_updated":"2024-03-07T14:43:38Z","department":[{"_id":"DaAl"}],"oa_version":"Preprint","abstract":[{"text":"We design fast deterministic algorithms for distance computation in the CONGESTED CLIQUE model. Our key contributions include:\r\n\r\n - A (2+ε)-approximation for all-pairs shortest paths problem in O(log²n / ε) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.\r\n - A (1+ε)-approximation for multi-source shortest paths problem from O(√n) sources in O(log² n / ε) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.\r\n\r\nOur main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in Õ(n^{1/6}) rounds.","lang":"eng"}],"month":"08","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1903.05956"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781450362177"]},"publication_status":"published","related_material":{"record":[{"relation":"later_version","status":"public","id":"7939"}]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"ista":"Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2019. Fast approximate shortest paths in the congested clique. Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin. PODC: Symposium on Principles of Distributed Computing, 74–83.","chicago":"Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf. “Fast Approximate Shortest Paths in the Congested Clique.” In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin, 74–83. ACM, 2019. https://doi.org/10.1145/3293611.3331633.","short":"K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, in:, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin, ACM, 2019, pp. 74–83.","ieee":"K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate shortest paths in the congested clique,” in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin, Toronto, ON, Canada, 2019, pp. 74–83.","apa":"Censor-Hillel, K., Dory, M., Korhonen, J., & Leitersdorf, D. (2019). Fast approximate shortest paths in the congested clique. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin (pp. 74–83). Toronto, ON, Canada: ACM. https://doi.org/10.1145/3293611.3331633","ama":"Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest paths in the congested clique. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin. ACM; 2019:74-83. doi:10.1145/3293611.3331633","mla":"Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested Clique.” Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin, ACM, 2019, pp. 74–83, doi:10.1145/3293611.3331633."},"title":"Fast approximate shortest paths in the congested clique","author":[{"last_name":"Censor-Hillel","full_name":"Censor-Hillel, Keren","first_name":"Keren"},{"last_name":"Dory","full_name":"Dory, Michal","first_name":"Michal"},{"id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne","full_name":"Korhonen, Janne","last_name":"Korhonen"},{"full_name":"Leitersdorf, Dean","last_name":"Leitersdorf","first_name":"Dean"}],"external_id":{"arxiv":["1903.05956"],"isi":["000570442000011"]},"article_processing_charge":"No","publisher":"ACM","quality_controlled":"1","oa":1,"day":"01","publication":"Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin","isi":1,"year":"2019","date_published":"2019-08-01T00:00:00Z","doi":"10.1145/3293611.3331633","date_created":"2019-10-08T12:48:42Z","page":"74-83"}]