{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:42Z","timestamp":1781078262948,"version":"3.54.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,2,2]],"date-time":"2016-02-02T00:00:00Z","timestamp":1454371200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,2,2]],"date-time":"2016-02-02T00:00:00Z","timestamp":1454371200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["246\/08 and 1536\/14"],"award-info":[{"award-number":["246\/08 and 1536\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217423 and CCF-1065125"],"award-info":[{"award-number":["CCF-1217423 and CCF-1065125"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217423 and CCF-1065125"],"award-info":[{"award-number":["CCF-1217423 and CCF-1065125"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1536\/14"],"award-info":[{"award-number":["1536\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217423, CCF-1065125, CCF-1420692"],"award-info":[{"award-number":["CCF-1217423, CCF-1065125, CCF-1420692"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00453-016-0126-y","type":"journal-article","created":{"date-parts":[[2016,2,2]],"date-time":"2016-02-02T20:41:23Z","timestamp":1454445683000},"page":"971-994","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Local Computation Algorithms for Graphs of Non-constant Degrees"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3167-1766","authenticated-orcid":false,"given":"Reut","family":"Levi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anak","family":"Yodpinyanee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,2,2]]},"reference":[{"issue":"2","key":"126_CR1","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/s00453-007-9075-9","volume":"51","author":"N Ailon","year":"2008","unstructured":"Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Property-preserving data reconstruction. Algorithmica 51(2), 160\u2013182 (2008)","journal-title":"Algorithmica"},{"issue":"4","key":"126_CR2","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1002\/rsa.3240020403","volume":"2","author":"N Alon","year":"1991","unstructured":"Alon, N.: A parallel algorithmic version of the local lemma. Random Struct. Algorithms 2(4), 367\u2013378 (1991)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"126_CR3","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"126_CR4","doi-asserted-by":"crossref","unstructured":"Alon, N., Rubinfeld, R., Vardi, S., Xie, N.: Space-efficient local computation algorithms. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1132\u20131139. SIAM (2012)","DOI":"10.1137\/1.9781611973099.89"},{"key":"126_CR5","doi-asserted-by":"crossref","unstructured":"Andersen, R., Chung, F., Lang, K.: Local graph partitioning using pagerank vectors. In: Foundations of Computer Science, 2006. FOCS\u201906. 47th Annual IEEE Symposium on, pp. 475\u2013486. IEEE (2006)","DOI":"10.1109\/FOCS.2006.44"},{"key":"126_CR6","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. In: Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pp. 321\u2013330. IEEE (2012)","DOI":"10.1109\/FOCS.2012.60"},{"issue":"4","key":"126_CR7","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J Beck","year":"1991","unstructured":"Beck, J.: An algorithmic approach to the Lov\u00e1sz local lemma. I. Random Struct. Algorithms 2(4), 343\u2013365 (1991)","journal-title":"Random Struct. Algorithms"},{"key":"126_CR8","doi-asserted-by":"crossref","unstructured":"Borgs, C., Brautbar, M., Chayes, J.T., Khanna, S., Lucier, B.: The power of local information in social networks. In: Goldberg, P.W. (ed.) Internet and Network Economics, Proceedings of the 8th International Workshop, WINE 2012, Liverpool, UK, December 10\u201312, 2012. Lecture Notes in Computer Science, vol. 7695, pp. 406\u2013419. Springer (2012)","DOI":"10.1007\/978-3-642-35311-6_30"},{"key":"126_CR9","unstructured":"Brakerski, Z.: Local property restoring. Unpublished manuscript (2008)"},{"key":"126_CR10","unstructured":"Campagna, A., Guo, A., Rubinfeld, R.: Local reconstructors and tolerant testers for connectivity and diameter. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Proceedings of the 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21\u201323, 2013. Lecture Notes in Computer Science, vol. 8096, pp. 411\u2013424. Springer, Berlin (2013)"},{"issue":"4","key":"126_CR11","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1989727.1989728","volume":"58","author":"B Chazelle","year":"2011","unstructured":"Chazelle, B., Seshadhri, C.: Online geometric reconstruction. J. ACM (JACM) 58(4), 14 (2011)","journal-title":"J. ACM (JACM)"},{"key":"126_CR12","doi-asserted-by":"crossref","unstructured":"Chung, K.M., Pettie, S., Su, H.H.: Distributed algorithms for the lov\u00e1sz local lemma and graph coloring. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, pp. 134\u2013143. ACM (2014)","DOI":"10.1145\/2611462.2611465"},{"key":"126_CR13","unstructured":"Dutta, A., Levi, R., Ron, D., Rubinfeld, R.: A simple online competitive adaptation of lempel-ziv compression with efficient random access support. In: Data Compression Conference (DCC), 2013, pp. 113\u2013122. IEEE (2013)"},{"key":"126_CR14","doi-asserted-by":"crossref","unstructured":"Even, G., Medina, M., Ron, D.: Deterministic stateless centralized local algorithms for bounded degree graphs. In: Schulz, A.S., Wagner, D. (eds.) Algorithms - ESA 2014, Proceedings of the 22th Annual European Symposium, Wroclaw, Poland, September 8\u201310, 2014. Lecture Notes in Computer Science, vol. 8737, pp. 394\u2013405. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-44777-2_33"},{"key":"126_CR15","doi-asserted-by":"crossref","unstructured":"Even, G., Medina, M., Ron, D.: Distributed maximum matching in bounded degree graphs. arXiv preprint arXiv:1407.7882 (2014)","DOI":"10.1145\/2684464.2684469"},{"key":"126_CR16","doi-asserted-by":"crossref","unstructured":"Gamarnik, D., Sudan, M.: Limits of local algorithms over sparse random graphs. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, pp. 369\u2013376. ACM (2014)","DOI":"10.1145\/2554797.2554831"},{"key":"126_CR17","doi-asserted-by":"crossref","unstructured":"Hassidim, A., Mansour, Y., Vardi, S.: Local computation mechanism design. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation, pp. 601\u2013616. ACM (2014)","DOI":"10.1145\/2600057.2602839"},{"issue":"4","key":"126_CR18","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"126_CR19","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A Israeli","year":"1986","unstructured":"Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett. 22(2), 77\u201380 (1986)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"126_CR20","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1137\/110840741","volume":"42","author":"M Jha","year":"2013","unstructured":"Jha, M., Raskhodnikova, S.: Testing and reconstruction of lipschitz functions with applications to data privacy. SIAM J. Comput. 42(2), 700\u2013731 (2013)","journal-title":"SIAM J. Comput."},{"key":"126_CR21","doi-asserted-by":"crossref","unstructured":"Kale, S., Peres, Y., Seshadhri, C.: Noise tolerance of expanders and sublinear expander reconstruction. In: Foundations of Computer Science, 2008. FOCS\u201908. IEEE 49th Annual IEEE Symposium on, pp. 719\u2013728. IEEE (2008)","DOI":"10.1109\/FOCS.2008.65"},{"key":"126_CR22","doi-asserted-by":"crossref","unstructured":"Kelsen, P.: Fast parallel matching in expander graphs. In: Proceedings of the Fifth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 293\u2013299. ACM (1993)","DOI":"10.1145\/165231.166107"},{"key":"126_CR23","unstructured":"Levi, R., Ron, D., Rubinfeld, R.: Local algorithms for sparse spanning graphs. In: Jansen, K., Rolim, J.D.P., Devanur, N.R., Moore, C. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2014, September 4\u20136, 2014, Barcelona, Spain. LIPIcs, vol. 28, p. 826. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014)"},{"issue":"1","key":"126_CR24","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."},{"issue":"2","key":"126_CR25","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1137\/080714403","volume":"39","author":"Z Lotker","year":"2009","unstructured":"Lotker, Z., Patt-Shamir, B., Ros\u00e9n, A.: Distributed approximate matching. SIAM J. Comput. 39(2), 445\u2013460 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"126_CR26","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"126_CR27","doi-asserted-by":"crossref","unstructured":"Mansour, Y., Rubinstein, A., Vardi, S., Xie, N.: Converting online algorithms to local computation algorithms. In: Czumaj, A., Mehlhorn, K., Pitts, A.M., Wattenhofer, R. (eds.) Automata, Languages, and Programming, Proceedings of the 39th International Colloquium, ICALP 2012, Warwick, UK, July 9\u201313, 2012. Lecture Notes in Computer Science, vol. 7391, pp. 653\u2013664. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-31594-7_55"},{"key":"126_CR28","doi-asserted-by":"crossref","unstructured":"Mansour, Y., Vardi, S.: A local computation approximation scheme to maximum matching. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 260\u2013273. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-40328-6_19"},{"issue":"2","key":"126_CR29","first-page":"22","volume":"5","author":"S Marko","year":"2009","unstructured":"Marko, S., Ron, D.: Approximating the distance to properties in bounded-degree and general sparse graphs. ACM Trans. Algorithms (TALG) 5(2), 22 (2009)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"126_CR30","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Strauss, M., Zheng, X.: Workload-optimal histograms on streams. In: Brodal, G.S., Leonardi, S. (eds.) Algorithms - ESA 2005, Proceedings of the 13th Annual European Symposium, Palma de Mallorca, Spain, October 3\u20136, 2005. Lecture Notes in Computer Science, vol. 3669, pp. 734\u2013745. Springer, Berlin (2005)","DOI":"10.1007\/11561071_65"},{"key":"126_CR31","doi-asserted-by":"crossref","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Foundations of Computer Science, 2008. FOCS\u201908. IEEE 49th Annual IEEE Symposium on, pp. 327\u2013336. IEEE (2008)","DOI":"10.1109\/FOCS.2008.81"},{"key":"126_CR32","doi-asserted-by":"crossref","unstructured":"Onak, K., Ron, D., Rosen, M., Rubinfeld, R.: A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1123\u20131131. SIAM (2012)","DOI":"10.1137\/1.9781611973099.88"},{"key":"126_CR33","doi-asserted-by":"crossref","unstructured":"Orecchia, L., Zhu, Z.A.: Flow-based algorithms for local graph clustering. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1267\u20131286. SIAM (2014)","DOI":"10.1137\/1.9781611973402.94"},{"issue":"1","key":"126_CR34","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.tcs.2007.04.040","volume":"381","author":"M Parnas","year":"2007","unstructured":"Parnas, M., Ron, D.: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theor. Comput. Sci. 381(1), 183\u2013196 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"126_CR35","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. Siam, Philadelphia. Technical report, ISBN 0-89871-464-8 (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"126_CR36","unstructured":"Reingold, O., Vardi, S.: New techniques and tighter bounds for local computation algorithms. arXiv preprint arXiv:1404.5398 (2014)"},{"key":"126_CR37","unstructured":"Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: Innovations in Computer Science\u2014ICS 2010, Tsinghua University, Beijing, China, January 7\u20139, 2011. Proceedings, pp. 223\u2013238 (2011). http:\/\/conference.itcs.tsinghua.edu.cn\/ICS2011\/content\/papers\/36.html"},{"issue":"7","key":"126_CR38","doi-asserted-by":"publisher","first-page":"2897","DOI":"10.1137\/080728561","volume":"39","author":"M Saks","year":"2010","unstructured":"Saks, M., Seshadhri, C.: Local monotonicity reconstruction. SIAM J. Comput. 39(7), 2897\u20132926 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"126_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/080744888","volume":"42","author":"DA Spielman","year":"2013","unstructured":"Spielman, D.A., Teng, S.H.: A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J. Comput. 42(1), 1\u201326 (2013)","journal-title":"SIAM J. Comput."},{"key":"126_CR40","doi-asserted-by":"crossref","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the xor lemma. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 537\u2013546. ACM (1999)","DOI":"10.1145\/301250.301397"},{"issue":"4","key":"126_CR41","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1137\/110828691","volume":"41","author":"Y Yoshida","year":"2012","unstructured":"Yoshida, Y., Yamamoto, M., Ito, H.: Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SIAM J. Comput. 41(4), 1074\u20131093 (2012)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0126-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0126-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0126-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0126-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,3]],"date-time":"2022-06-03T02:05:34Z","timestamp":1654221934000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0126-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,2]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["126"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0126-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,2]]},"assertion":[{"value":"11 March 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}