[{"department":[{"_id":"DaAl"}],"arxiv":1,"month":"08","citation":{"apa":"Censor-Hillel, K., Dory, M., Korhonen, J., &#38; Leitersdorf, D. (2019). Fast approximate shortest paths in the congested clique. In <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin</i> (pp. 74–83). Toronto, ON, Canada: ACM. <a href=\"https://doi.org/10.1145/3293611.3331633\">https://doi.org/10.1145/3293611.3331633</a>","mla":"Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested Clique.” <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin</i>, ACM, 2019, pp. 74–83, doi:<a href=\"https://doi.org/10.1145/3293611.3331633\">10.1145/3293611.3331633</a>.","chicago":"Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf. “Fast Approximate Shortest Paths in the Congested Clique.” In <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin</i>, 74–83. ACM, 2019. <a href=\"https://doi.org/10.1145/3293611.3331633\">https://doi.org/10.1145/3293611.3331633</a>.","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.","ieee":"K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate shortest paths in the congested clique,” in <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin</i>, Toronto, ON, Canada, 2019, pp. 74–83.","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.","ama":"Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest paths in the congested clique. In: <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin</i>. ACM; 2019:74-83. doi:<a href=\"https://doi.org/10.1145/3293611.3331633\">10.1145/3293611.3331633</a>"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa":1,"language":[{"iso":"eng"}],"date_created":"2019-10-08T12:48:42Z","author":[{"full_name":"Censor-Hillel, Keren","last_name":"Censor-Hillel","first_name":"Keren"},{"last_name":"Dory","full_name":"Dory, Michal","first_name":"Michal"},{"first_name":"Janne","full_name":"Korhonen, Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","last_name":"Korhonen"},{"full_name":"Leitersdorf, Dean","last_name":"Leitersdorf","first_name":"Dean"}],"day":"01","scopus_import":"1","oa_version":"Preprint","title":"Fast approximate shortest paths in the congested clique","publication_status":"published","publication_identifier":{"isbn":["9781450362177"]},"abstract":[{"lang":"eng","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."}],"isi":1,"year":"2019","external_id":{"isi":["000570442000011"],"arxiv":["1903.05956"]},"related_material":{"record":[{"id":"7939","status":"public","relation":"later_version"}]},"conference":{"location":"Toronto, ON, Canada","start_date":"2019-07-29","end_date":"2019-08-02","name":"PODC: Symposium on Principles of Distributed Computing"},"date_published":"2019-08-01T00:00:00Z","publication":"Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin","status":"public","date_updated":"2024-03-07T14:43:38Z","_id":"6933","type":"conference","doi":"10.1145/3293611.3331633","article_processing_charge":"No","publisher":"ACM","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1903.05956"}],"quality_controlled":"1","page":"74-83"},{"page":"259-261","main_file_link":[{"url":"https://arxiv.org/abs/1905.03012","open_access":"1"}],"quality_controlled":"1","doi":"10.1145/3293611.3331581","article_processing_charge":"No","publisher":"ACM","date_updated":"2023-09-08T11:37:22Z","_id":"6935","type":"conference","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"publication":"Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing","status":"public","ec_funded":1,"date_published":"2019-08-01T00:00:00Z","conference":{"end_date":"2019-08-02","start_date":"2019-07-29","name":"PODC: Symposium on Principles of Distributed Computing","location":"Toronto, ON, Canada"},"year":"2019","isi":1,"external_id":{"isi":["000570442000037"],"arxiv":["1905.03012"]},"abstract":[{"lang":"eng","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."}],"publication_identifier":{"isbn":["9781450362177"]},"publication_status":"published","author":[{"full_name":"Foerster, Klaus-Tycho","last_name":"Foerster","first_name":"Klaus-Tycho"},{"last_name":"Korhonen","full_name":"Korhonen, Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne"},{"orcid":"0000-0002-6432-6646","first_name":"Joel","full_name":"Rybicki, Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"}],"day":"01","scopus_import":"1","title":"Does preprocessing help under congestion?","oa_version":"Preprint","date_created":"2019-10-08T12:57:14Z","oa":1,"language":[{"iso":"eng"}],"citation":{"ama":"Foerster K-T, Korhonen J, Rybicki J, Schmid S. Does preprocessing help under congestion? In: <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing</i>. ACM; 2019:259-261. doi:<a href=\"https://doi.org/10.1145/3293611.3331581\">10.1145/3293611.3331581</a>","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.","ieee":"K.-T. Foerster, J. Korhonen, J. Rybicki, and S. Schmid, “Does preprocessing help under congestion?,” in <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing</i>, Toronto, ON, Canada, 2019, pp. 259–261.","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Joel Rybicki, and Stefan Schmid. “Does Preprocessing Help under Congestion?” In <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing</i>, 259–61. ACM, 2019. <a href=\"https://doi.org/10.1145/3293611.3331581\">https://doi.org/10.1145/3293611.3331581</a>.","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.","mla":"Foerster, Klaus-Tycho, et al. “Does Preprocessing Help under Congestion?” <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing</i>, ACM, 2019, pp. 259–61, doi:<a href=\"https://doi.org/10.1145/3293611.3331581\">10.1145/3293611.3331581</a>.","apa":"Foerster, K.-T., Korhonen, J., Rybicki, J., &#38; Schmid, S. (2019). Does preprocessing help under congestion? In <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing</i> (pp. 259–261). Toronto, ON, Canada: ACM. <a href=\"https://doi.org/10.1145/3293611.3331581\">https://doi.org/10.1145/3293611.3331581</a>"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","arxiv":1,"month":"08","department":[{"_id":"DaAl"}]}]