{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T23:27:40Z","timestamp":1678404460977},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["755839"]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1696\/14"]},{"DOI":"10.13039\/501100001742","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2015803"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,16]]},"DOI":"10.1145\/3293611.3331597","type":"proceedings-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:21Z","timestamp":1563542241000},"update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Hardness of Distributed Optimization"],"prefix":"10.1145","author":[{"given":"Nir","family":"Bacrach","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Keren","family":"Censor-Hillel","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Michal","family":"Dory","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Yuval","family":"Efron","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Dean","family":"Leitersdorf","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Ami","family":"Paz","sequence":"additional","affiliation":[{"name":"CNRS & Universit\u00e9 de Paris, Paris, France"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Even in Sparse Networks. In 30th International Symposium on Distributed Computing, DISC. 29--42","author":"Abboud Amir","year":"2016","unstructured":"Amir Abboud , Keren Censor-Hillel , and Seri Khoury . 2016 . Near-Linear Lower Bounds for Distributed Distance Computations , Even in Sparse Networks. In 30th International Symposium on Distributed Computing, DISC. 29--42 . Amir Abboud, Keren Censor-Hillel, and Seri Khoury. 2016. Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. In 30th International Symposium on Distributed Computing, DISC. 29--42."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331597"},{"key":"e_1_3_2_1_3_1","volume-title":"Parameterized Distributed Algorithms. CoRR","author":"Ben-Basat Ran","year":"2018","unstructured":"Ran Ben-Basat , Ken-ichi Kawarabayashi, and Gregory Schwartzman . 2018. Parameterized Distributed Algorithms. CoRR , Vol. abs\/ 1807 .04900 ( 2018 ). arxiv: 1807.04900 http:\/\/arxiv.org\/abs\/1807.04900 Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. 2018. Parameterized Distributed Algorithms. CoRR, Vol. abs\/1807.04900 (2018). arxiv: 1807.04900 http:\/\/arxiv.org\/abs\/1807.04900"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316326"},{"key":"e_1_3_2_1_5_1","volume-title":"25th International Colloquium, SIROCCO. 88--101","author":"Boppana Ravi B.","year":"2018","unstructured":"Ravi B. Boppana , Magn\u00fa s M. Halld\u00f3 rsson, and Dror Rawitz . 2018 . Simple and Local Independent Set Approximation. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO. 88--101 . Ravi B. Boppana, Magn\u00fa s M. Halld\u00f3 rsson, and Dror Rawitz. 2018. Simple and Local Independent Set Approximation. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO. 88--101."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212758"},{"key":"e_1_3_2_1_7_1","first-page":"1","article-title":"Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In 31st International Symposium on Distributed Computing","volume":"10","author":"Censor-Hillel Keren","year":"2017","unstructured":"Keren Censor-Hillel , Seri Khoury , and Ami Paz . 2017 a. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In 31st International Symposium on Distributed Computing , DISC. 10 : 1 -- 10 :16. Keren Censor-Hillel, Seri Khoury, and Ami Paz. 2017a. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In 31st International Symposium on Distributed Computing, DISC. 10:1--10:16.","journal-title":"DISC."},{"key":"e_1_3_2_1_8_1","volume-title":"24th International Colloquium, SIROCCO. 71--89","author":"Censor-Hillel Keren","year":"2017","unstructured":"Keren Censor-Hillel , Ami Paz , and Mor Perry . 2017 b. Approximate Proof-Labeling Schemes. In Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO. 71--89 . Keren Censor-Hillel, Ami Paz, and Mor Perry. 2017b. Approximate Proof-Labeling Schemes. In Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO. 71--89."},{"key":"e_1_3_2_1_9_1","volume-title":"Fast and Efficient Distributed Computation of Hamiltonian Cycles in Random Graphs. In 38th IEEE International Conference on Distributed Computing Systems, ICDCS. 764--774","author":"Chatterjee Soumyottam","year":"2018","unstructured":"Soumyottam Chatterjee , Reza Fathi , Gopal Pandurangan , and Nguyen Dinh Pham . 2018 . Fast and Efficient Distributed Computation of Hamiltonian Cycles in Random Graphs. In 38th IEEE International Conference on Distributed Computing Systems, ICDCS. 764--774 . Soumyottam Chatterjee, Reza Fathi, Gopal Pandurangan, and Nguyen Dinh Pham. 2018. Fast and Efficient Distributed Computation of Hamiltonian Cycles in Random Graphs. In 38th IEEE International Conference on Distributed Computing Systems, ICDCS. 764--774."},{"key":"e_1_3_2_1_10_1","first-page":"1","article-title":"Detecting Cliques in CONGEST Networks. In 32nd International Symposium on Distributed Computing","volume":"16","author":"Czumaj Artur","year":"2018","unstructured":"Artur Czumaj and Christian Konrad . 2018 . Detecting Cliques in CONGEST Networks. In 32nd International Symposium on Distributed Computing , DISC. 16 : 1 -- 16 :15. Artur Czumaj and Christian Konrad. 2018. Detecting Cliques in CONGEST Networks. In 32nd International Symposium on Distributed Computing, DISC. 16:1--16:15.","journal-title":"DISC."},{"key":"e_1_3_2_1_11_1","unstructured":"Erik Demaine. 2014. Lecture 10 in Algorithmic Lower Bounds. https:\/\/ocw.mit.edu\/courses\/electrical-engineering-and-computer-science\/6--890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014\/lecture-notes\/MIT6_890F14_Lec10.pdf. Erik Demaine. 2014. Lecture 10 in Algorithmic Lower Bounds. https:\/\/ocw.mit.edu\/courses\/electrical-engineering-and-computer-science\/6--890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014\/lecture-notes\/MIT6_890F14_Lec10.pdf."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210401"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095207"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M113277X"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_1_17_1","first-page":"1","article-title":"New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In 32nd International Symposium on Distributed Computing","volume":"31","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari and Jason Li . 2018 . New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In 32nd International Symposium on Distributed Computing , DISC. 31 : 1 -- 31 :16. Mohsen Ghaffari and Jason Li. 2018. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In 32nd International Symposium on Distributed Computing, DISC. 31:1--31:16.","journal-title":"DISC."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875499"},{"key":"e_1_3_2_1_19_1","first-page":"1","article-title":"Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In Proceedings of the 19th International Conference on Principles of Distributed Systems","volume":"6","author":"Holzer Stephan","year":"2015","unstructured":"Stephan Holzer and Nathan Pinsker . 2015 . Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In Proceedings of the 19th International Conference on Principles of Distributed Systems , OPODIS. 6 : 1 -- 6 :16. Stephan Holzer and Nathan Pinsker. 2015. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In Proceedings of the 19th International Conference on Principles of Distributed Systems, OPODIS. 6:1--6:16.","journal-title":"OPODIS."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332504"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/777474.777476"},{"key":"e_1_3_2_1_22_1","volume-title":"Reducibility Among Combinatorial Problems. In 50 Years of Integer Programming 1958--2008 - From the Early Years to the State-of-the-Art","author":"Karp Richard M.","unstructured":"Richard M. Karp . 2010. Reducibility Among Combinatorial Problems. In 50 Years of Integer Programming 1958--2008 - From the Early Years to the State-of-the-Art . Springer , 219--241. Richard M. Karp. 2010. Reducibility Among Combinatorial Problems. In 50 Years of Integer Programming 1958--2008 - From the Early Years to the State-of-the-Art. Springer, 219--241."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688093"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-004-0112-5"},{"key":"e_1_3_2_1_27_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press , New York, NY, USA . Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press, New York, NY, USA."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_3_2_1_30_1","volume-title":"Distributed Computing - 28th International Symposium, DISC. 439--453.","author":"Nanongkai Danupon","unstructured":"Danupon Nanongkai and Hsin-Hao Su. 2014. Almost-Tight Distributed Minimum Cut Algorithms . In Distributed Computing - 28th International Symposium, DISC. 439--453. Danupon Nanongkai and Hsin-Hao Su. 2014. Almost-Tight Distributed Minimum Cut Algorithms. In Distributed Computing - 28th International Symposium, DISC. 439--453."},{"key":"e_1_3_2_1_31_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Nisan Noam","unstructured":"Noam Nisan . 2002. The communication complexity of approximate set packing and covering . In International Colloquium on Automata, Languages, and Programming , ICALP. Springer , 868--875. Noam Nisan. 2002. The communication complexity of approximate set packing and covering. In International Colloquium on Automata, Languages, and Programming, ICALP. Springer, 868--875."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369740"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_1_36_1","volume-title":"25th International Colloquium, SIROCCO. 72--87","author":"Turau Volker","year":"2018","unstructured":"Volker Turau . 2018 . A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO. 72--87 . Volker Turau. 2018. A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO. 72--87."},{"key":"e_1_3_2_1_37_1","volume-title":"Approximation algorithms","author":"Vazirani Vijay V.","unstructured":"Vijay V. Vazirani . 2001. Approximation algorithms . Springer . http:\/\/www.springer.com\/computer\/theoretical computer science\/book\/978-3-540-65367-7 Vijay V. Vazirani. 2001. Approximation algorithms.Springer. http:\/\/www.springer.com\/computer\/theoretical computer science\/book\/978-3-540-65367-7"}],"event":{"name":"PODC '19: ACM Symposium on Principles of Distributed Computing","location":"Toronto ON Canada","acronym":"PODC '19","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331597","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T18:34:15Z","timestamp":1673202855000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331597"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":37,"alternative-id":["10.1145\/3293611.3331597","10.1145\/3293611"],"URL":"http:\/\/dx.doi.org\/10.1145\/3293611.3331597","relation":{},"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}