{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:41:54Z","timestamp":1787017314633,"version":"build-2736575974"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,3,31]],"date-time":"2016-03-31T00:00:00Z","timestamp":1459382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,5,4]]},"abstract":"<jats:p>\n                    The question of what can be computed, and how efficiently, is at the core of computer science. Not surprisingly, in distributed systems and networking research, an equally fundamental question is what can be computed in a\n                    <jats:italic>distributed<\/jats:italic>\n                    fashion. More precisely, if nodes of a network must base their decision on information in their local neighborhood only, how well can they compute or approximate a global (optimization) problem? In this paper we give the first polylogarithmic lower bound on such local computation for (optimization) problems including minimum vertex cover, minimum (connected) dominating set, maximum matching, maximal independent set, and maximal matching. In addition, we present a new distributed algorithm for solving general covering and packing linear programs. For some problems this algorithm is tight with the lower bounds, whereas for others it is a distributed approximation scheme. Together, our lower and upper bounds establish the local computability and approximability of a large class of problems, characterizing how much local information is required to solve these tasks.\n                  <\/jats:p>","DOI":"10.1145\/2742012","type":"journal-article","created":{"date-parts":[[2016,3,31]],"date-time":"2016-03-31T07:55:39Z","timestamp":1459410939000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":115,"title":["Local Computation"],"prefix":"10.1145","volume":"63","author":[{"given":"Fabian","family":"Kuhn","sequence":"first","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Moscibroda","sequence":"additional","affiliation":[{"name":"Microsoft Research, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,3,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"WDAG (Lecture Notes in Computer Science), Jan van Leeuwen and Nicola Santoro (Eds.)","author":"Afek Yehuda","unstructured":"Yehuda Afek , Shay Kutten , and Moti Yung . 1990. Memory-efficient self stabilizing protocols for general networks . In WDAG (Lecture Notes in Computer Science), Jan van Leeuwen and Nicola Santoro (Eds.) , Vol. 486 . Springer , Berlin , 15--28. Yehuda Afek, Shay Kutten, and Moti Yung. 1990. Memory-efficient self stabilizing protocols for general networks. In WDAG (Lecture Notes in Computer Science), Jan van Leeuwen and Nicola Santoro (Eds.), Vol. 486. Springer, Berlin, 15--28."},{"key":"e_1_2_1_2_1","unstructured":"J. Akiyama H. Era and F. Harary. 1983. Regular graphs containing a given graph. Elem. Math. 83 83 (1983) 15--17.  J. Akiyama H. Era and F. Harary. 1983. Regular graphs containing a given graph. Elem. Math. 83 83 (1983) 15--17."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(81)90062-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21938"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185377"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"R. Bar-Yehuda K. Censor-Hillel and G. Schwartzman. 2016. A distributed (2 &plus; &epsi;)-approximation for vertex cover in O(log&thinsp;\u0394\/&epsi;log&thinsp;log&thinsp;\u0394) rounds. CoRR abs\/1602.03713v2.  R. Bar-Yehuda K. Censor-Hillel and G. Schwartzman. 2016. A distributed (2 &plus; &epsi;)-approximation for vertex cover in O (log&thinsp;\u0394\/&epsi;log&thinsp;log&thinsp;\u0394) rounds. CoRR abs\/1602.03713v2 .","DOI":"10.1145\/2933057.2933086"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers.  L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-02009-4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646119"},{"key":"e_1_2_1_10_1","volume-title":"Extremal Graph Theory","author":"Bollobas B.","unstructured":"B. Bollobas . 1978. Extremal Graph Theory . Academic Press . B. Bollobas. 1978. Extremal Graph Theory. Academic Press."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"e_1_2_1_13_1","volume-title":"Mohammad Taghi Hajiaghayi, and Mohammad R. Salavatipour","author":"Demaine Erik D.","year":"2006","unstructured":"Erik D. Demaine , Uriel Feige , Mohammad Taghi Hajiaghayi, and Mohammad R. Salavatipour . 2006 . Combination can be hard: Approximability of the unique coverage problem. In Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithm (SODA). 162--171. Erik D. Demaine, Uriel Feige, Mohammad Taghi Hajiaghayi, and Mohammad R. Salavatipour. 2006. Combination can be hard: Approximability of the unique coverage problem. In Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithm (SODA). 162--171."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_2_1_15_1","volume-title":"Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 717--724","author":"Dubhashi D.","unstructured":"D. Dubhashi , A. Mei , A. Panconesi , J. Radhakrishnan , and A. Srinivasan . 2003. Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons . In Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 717--724 . D. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, and A. Srinivasan. 2003. Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. In Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 717--724."},{"key":"e_1_2_1_16_1","volume-title":"Distributed approximation\u2014A survey. ACM SIGACT News\u2014Distributed Computing Column 35, 4","author":"Elkin Michael","year":"2004","unstructured":"Michael Elkin . 2004a. Distributed approximation\u2014A survey. ACM SIGACT News\u2014Distributed Computing Column 35, 4 ( 2004 ). Michael Elkin. 2004a. Distributed approximation\u2014A survey. ACM SIGACT News\u2014Distributed Computing Column 35, 4 (2004)."},{"key":"e_1_2_1_17_1","volume-title":"Proc. of the 36th ACM Symposium on Theory of Computing (STOC). 331--340","author":"Elkin Michael","year":"2004","unstructured":"Michael Elkin . 2004 b. An unconditional lower bound on the hardness of approximation of distributed minimum spanning tree problem . In Proc. of the 36th ACM Symposium on Theory of Computing (STOC). 331--340 . Michael Elkin. 2004b. An unconditional lower bound on the hardness of approximation of distributed minimum spanning tree problem. In Proc. of the 36th ACM Symposium on Theory of Computing (STOC). 331--340."},{"key":"e_1_2_1_18_1","first-page":"251","article-title":"Regul\u00e4re graphen gegebener taillenweite mit minimaler knotenzahl","volume":"12","author":"Erd\u0151s P.","year":"1963","unstructured":"P. Erd\u0151s and H. Sachs . 1963 . Regul\u00e4re graphen gegebener taillenweite mit minimaler knotenzahl . Wiss. Z. Martin-Luther-U. Halle Math.-Nat. 12 (1963), 251 -- 257 . P. Erd\u0151s and H. Sachs. 1963. Regul\u00e4re graphen gegebener taillenweite mit minimaler knotenzahl. Wiss. Z. Martin-Luther-U. Halle Math.-Nat. 12 (1963), 251--257.","journal-title":"Wiss. Z. Martin-Luther-U. Halle Math.-Nat."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700380754"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-003-0091-y"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499228"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2005.198"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_2_1_26_1","volume-title":"Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC). 33--42","author":"Jia L.","unstructured":"L. Jia , R. Rajaraman , and R. Suel . 2001. An efficient distributed algorithm for constructing small dominating sets . In Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC). 33--42 . L. Jia, R. Rajaraman, and R. Suel. 2001. An efficient distributed algorithm for constructing small dominating sets. In Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC). 33--42."},{"key":"e_1_2_1_27_1","volume-title":"Proc. of the 23rd ACM Symposium on the Principles of Distributed Computing (PODC). 300--309","author":"Kuhn Fabian","year":"2004","unstructured":"Fabian Kuhn , Thomas Moscibroda , and Roger Wattenhofer . 2004 . What cannot be computed locally&excl; . In Proc. of the 23rd ACM Symposium on the Principles of Distributed Computing (PODC). 300--309 . Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. 2004. What cannot be computed locally&excl;. In Proc. of the 23rd ACM Symposium on the Principles of Distributed Computing (PODC). 300--309."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109666"},{"key":"e_1_2_1_29_1","volume-title":"Proc. of the 22nd Annual ACM Symp. on Principles of Distributed Computing (PODC). 25--32","author":"Kuhn F.","unstructured":"F. Kuhn and R. Wattenhofer . 2003. Constant-time distributed dominating set approximation . In Proc. of the 22nd Annual ACM Symp. on Principles of Distributed Computing (PODC). 25--32 . F. Kuhn and R. Wattenhofer. 2003. Constant-time distributed dominating set approximation. In Proc. of the 22nd Annual ACM Symp. on Principles of Distributed Computing (PODC). 25--32."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00058-L"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378540"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05118-0_2"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_27"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_2_1_40_1","volume-title":"Proc. of the 49th Symposium on Foundations of Computer Science (FOCS). 327--336","author":"Huy","unstructured":"Huy N. Nguyen and Krzysztof Onak. 2008. Constant-time approximation algorithms via local improvements . In Proc. of the 49th Symposium on Foundations of Computer Science (FOCS). 327--336 . Huy N. Nguyen and Krzysztof Onak. 2008. Constant-time approximation algorithms via local improvements. In Proc. of the 49th Symposium on Foundations of Computer Science (FOCS). 327--336."},{"key":"e_1_2_1_41_1","volume-title":"Proc. of the 10th ACM Symposium on Principles of Distributed Computing (PODC). 61--64","author":"Papadimitriou C. H.","unstructured":"C. H. Papadimitriou and M. Yannakakis . 1991. On the value of information in distributed decision making . In Proc. of the 10th ACM Symposium on Principles of Distributed Computing (PODC). 61--64 . C. H. Papadimitriou and M. Yannakakis. 1991. On the value of information in distributed decision making. In Proc. of the 10th ACM Symposium on Principles of Distributed Computing (PODC). 61--64."},{"key":"e_1_2_1_42_1","volume-title":"Proc. of the 25th ACM Symposium on Theory of Computing (STOC). 121--129","author":"Papadimitriou C. H.","unstructured":"C. H. Papadimitriou and M. Yannakakis . 1993. Linear programming without the matrix . In Proc. of the 25th ACM Symposium on Theory of Computing (STOC). 121--129 . C. H. Papadimitriou and M. Yannakakis. 1993. Linear programming without the matrix. In Proc. of the 25th ACM Symposium on Theory of Computing (STOC). 121--129."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1280283.1280327"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/3219302.3219303"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793260763"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400758"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.010"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225138"},{"key":"e_1_2_1_51_1","volume-title":"1st Innovations in Computer Science (ICS).","author":"Sterling Aaron","unstructured":"Aaron Sterling . 2009. Memory consistency conditions for self-assembly programming . In 1st Innovations in Computer Science (ICS). Beijing, China , 490--500. Aaron Sterling. 2009. Memory consistency conditions for self-assembly programming. In 1st Innovations in Computer Science (ICS). Beijing, China, 490--500."},{"key":"e_1_2_1_52_1","volume-title":"Survey of local algorithms. ACM Computing Surveys 45, 2","author":"Suomela J.","year":"2011","unstructured":"J. Suomela . 2011. Survey of local algorithms. ACM Computing Surveys 45, 2 ( 2011 ), 24:1--24:40. J. Suomela. 2011. Survey of local algorithms. ACM Computing Surveys 45, 2 (2011), 24:1--24:40."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30186-8_24"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959930"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2742012","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2742012","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:12:38Z","timestamp":1750212758000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2742012"}},"subtitle":["Lower and Upper Bounds"],"short-title":[],"issued":{"date-parts":[[2016,3,31]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,5,4]]}},"alternative-id":["10.1145\/2742012"],"URL":"https:\/\/doi.org\/10.1145\/2742012","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,31]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}