{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:14:30Z","timestamp":1750306470736,"version":"3.41.0"},"publisher-location":"Cham","reference-count":75,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319587462"},{"type":"electronic","value":"9783319587479"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-58747-9_6","type":"book-chapter","created":{"date-parts":[[2017,5,5]],"date-time":"2017-05-05T01:14:05Z","timestamp":1493946845000},"page":"38-47","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Can We Locally Compute Sparse Connected Subgraphs?"],"prefix":"10.1007","author":[{"given":"Ronitt","family":"Rubinfeld","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,6]]},"reference":[{"issue":"2","key":"6_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"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Rubinfeld, R., Vardi, S., Xie, N.: Space-efficient local computation algorithms. In: 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), Kyoto, January 2012","DOI":"10.1137\/1.9781611973099.89"},{"issue":"1\u20132","key":"6_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1080\/15427951.2008.10129302","volume":"5","author":"R Andersen","year":"2008","unstructured":"Andersen, R., Borgs, C., Chayes, J., Hopcroft, J., Mirrokni, V., Teng, S.: Local computation of pagerank contributions. Internet Math. 5(1\u20132), 23\u201345 (2008)","journal-title":"Internet Math."},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Andersen, R., Chung, F., Lang, K.: Local graph partitioning using pagerank vectors. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 475\u2013486 (2006)","DOI":"10.1109\/FOCS.2006.44"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Andersen, R., Peres, Y.: Finding sparse cuts locally using evolving sets. In: Proceedings of the 41st Annual ACM Symposium on the Theory of Computing, pp. 235\u2013244 (2009)","DOI":"10.1145\/1536414.1536449"},{"issue":"3","key":"6_CR6","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S Arora","year":"2003","unstructured":"Arora, S., Sudan, M.: Improved low-degree testing and its applications. Combinatorica 23(3), 365\u2013426 (2003)","journal-title":"Combinatorica"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-32512-0_32","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"P Awasthi","year":"2012","unstructured":"Awasthi, P., Jha, M., Molinaro, M., Raskhodnikova, S.: Limitations of local filters of Lipschitz and monotone functions. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM-2012. LNCS, vol. 7408, pp. 374\u2013386. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-32512-0_32"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Distributed ($$\\Delta +1$$)-coloring in linear (in $$\\Delta $$) time. In: Proceedings of the 41st Annual ACM Symposium on the Theory of Computing, pp. 111\u2013120 (2009)","DOI":"10.1145\/1536414.1536432"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. In: Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, pp. 410\u2013419 (2010)","DOI":"10.1145\/1835698.1835797"},{"issue":"3","key":"6_CR10","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/2903137","volume":"63","author":"L Barenboim","year":"2016","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 20 (2016)","journal-title":"J. ACM"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Ben-Aroya, A., Efremenko, K., Ta-Shma, A.: Local list-decoding with a constant number of queries, Technical report TR10-047, Electronic Colloquium on Computational Complexity, April 2010","DOI":"10.1109\/FOCS.2010.88"},{"issue":"1","key":"6_CR12","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1080\/15427951.2006.10129116","volume":"3","author":"P Berkhin","year":"2006","unstructured":"Berkhin, P.: Bookmark-coloring algorithm for personalized pagerank computing. Internet Mathematics 3(1), 41\u201362 (2006)","journal-title":"Internet Mathematics"},{"issue":"2","key":"6_CR13","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1137\/100808186","volume":"26","author":"A Bhattacharyya","year":"2012","unstructured":"Bhattacharyya, A., Grigorescu, E., Jha, M., Jung, K., Raskhodnikova, S., Woodruff, D.P.: Lower bounds for local monotonicity reconstruction from transitive-closure spanners. SIAM J. Discrete Math. 26(2), 618\u2013646 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-642-40328-6_29","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A Campagna","year":"2013","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.) APPROX\/RANDOM-2013. LNCS, vol. 8096, pp. 411\u2013424. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-40328-6_29"},{"issue":"6","key":"6_CR15","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B Chazelle","year":"2005","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput. 34(6), 1370\u20131379 (2005)","journal-title":"SIAM J. Comput."},{"key":"6_CR16","unstructured":"Cornejo, A.: Local distributed algorithms for multi-robot systems. Ph.D. thesis, MIT (2012)"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1007\/978-3-642-04355-0_50","volume-title":"Distributed Computing","author":"A Cornejo","year":"2009","unstructured":"Cornejo, A., Kuhn, F., Ley-Wild, R., Lynch, N.: Keeping mobile robot swarms connected. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 496\u2013511. Springer, Heidelberg (2009). doi:10.1007\/978-3-642-04355-0_50"},{"issue":"1","key":"6_CR18","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S0097539703435297","volume":"35","author":"A Czumaj","year":"2005","unstructured":"Czumaj, A., Ergun, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., Sohler, C.: Sublinear-time approximation of euclidean minimum spanning tree. SIAM J. Comput. 35(1), 91\u2013109 (2005)","journal-title":"SIAM J. Comput."},{"key":"6_CR19","first-page":"23","volume":"89","author":"A Czumaj","year":"2006","unstructured":"Czumaj, A., Sohler, C.: Sublinear-time algorithms. Bull. Eur. Assoc. Theor. Comput. Sci. 89, 23\u201347 (2006)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"issue":"3","key":"6_CR20","doi-asserted-by":"publisher","first-page":"904","DOI":"10.1137\/060672121","volume":"39","author":"A Czumaj","year":"2009","unstructured":"Czumaj, A., Sohler, C.: Estimating the weight of metric minimum spanning trees in sublinear time. SIAM J. Comput. 39(3), 904\u2013922 (2009)","journal-title":"SIAM J. Comput."},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Dutta, A., Levi, R., Ron, D., Rubinfeld, R.: A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support. In: Proceedings of the Data Compression Conference (DCC), pp. 113\u2013122 (2013)","DOI":"10.1109\/DCC.2013.19"},{"issue":"4","key":"6_CR22","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s00224-006-1266-2","volume":"41","author":"M Elkin","year":"2007","unstructured":"Elkin, M., Peleg, D.: The hardness of approximating spanner problems. Theor. Comput. Syst. 41(4), 691\u2013729 (2007)","journal-title":"Theor. Comput. Syst."},{"key":"6_CR23","unstructured":"Even, G., Medina, M., Ron, D.: Best of two local models: local centralized and local distributed algorithms. CoRR abs\/1402.3796 (2014). http:\/\/arxiv.org\/abs\/1402.3796"},{"key":"6_CR24","unstructured":"Feigenbaum, D.B.J.: Hiding instances in multi-oracle queries. In: Proceedings of the 7th Annual STACS Conference, pp. 34\u201348 (1990)"},{"key":"6_CR25","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0222061","volume":"22","author":"J Feigenbaum","year":"1993","unstructured":"Feigenbaum, J., Fortnow, L.: Random self-reducibility of complete sets. SIAM J. Comput. 22, 994\u20131005 (1993)","journal-title":"SIAM J. Comput."},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 690\u2013696 (2007)","DOI":"10.1016\/j.tcs.2006.12.012"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local distributed decision. CoRR abs\/1011.2152 (2010)","DOI":"10.1109\/FOCS.2011.17"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., Wigderson, A.: Self-testing\/correcting for polynomials and for approximate functions. In: Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing, pp. 32\u201342 (1991)","DOI":"10.1145\/103418.103429"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, 10\u201312 January 2016, pp. 270\u2013277 (2016). http:\/\/dx.doi.org\/10.1137\/1.9781611974331.ch20","DOI":"10.1137\/1.9781611974331.ch20"},{"issue":"4","key":"6_CR30","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1137\/S0895480198344540","volume":"13","author":"O Goldreich","year":"2000","unstructured":"Goldreich, O., Rubinfeld, R., Sudan, M.: Learning polynomials with queries: the highly noisy case. SIAM J. Discrete Math. 13(4), 535\u2013570 (2000)","journal-title":"SIAM J. Discrete Math."},{"key":"6_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/11780441_27","volume-title":"Combinatorial Pattern Matching","author":"R Gonz\u00e1lez","year":"2006","unstructured":"Gonz\u00e1lez, R., Navarro, G.: Statistical encoding of succinct data structures. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol. 4009, pp. 294\u2013306. Springer, Heidelberg (2006). doi:10.1007\/11780441_27"},{"key":"6_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-662-53426-7_15","volume-title":"Distributed Computing","author":"M G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Levi, R., Medina, M., Suomela, J.: Non-local probes do not help with many graph problems. In: Gavoille, C., Ilcinkas, D. (eds.) DISC 2016. LNCS, vol. 9888, pp. 201\u2013214. Springer, Heidelberg (2016). doi:10.1007\/978-3-662-53426-7_15"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Klivans, A.R., Zuckerman, D.: List-decoding Reed Muller codes over small fields. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 265\u2013274 (2008)","DOI":"10.1145\/1374376.1374417"},{"key":"6_CR34","doi-asserted-by":"crossref","unstructured":"Hasidim, A., Kelner, J., Nguyen, H.N., Onak, K.: Local graph partitions for approximation and testing. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 22\u201331 (2009)","DOI":"10.1109\/FOCS.2009.77"},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Hassidim, A., Mansour, Y., Vardi, S.: Local computation mechanism design. CoRR abs\/1311.3939 (2013)","DOI":"10.1145\/2600057.2602839"},{"key":"6_CR36","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: derandomizing the XOR lemma. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"key":"6_CR37","doi-asserted-by":"crossref","unstructured":"Jeh, G., Widom, J.: Scaling personalized web search. In: Proceedings of the 12th International Conference on World Wide Web, pp. 271\u2013279 (2003)","DOI":"10.1145\/775152.775191"},{"issue":"2","key":"6_CR38","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."},{"issue":"1","key":"6_CR39","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/110837863","volume":"42","author":"S Kale","year":"2013","unstructured":"Kale, S., Peres, Y., Seshadhri, C.: Noise tolerance of expanders and sublinear expansion reconstruction. SIAM J. Comput. 42(1), 305\u2013323 (2013)","journal-title":"SIAM J. Comput."},{"key":"6_CR40","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, pp. 80\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"key":"6_CR41","doi-asserted-by":"crossref","unstructured":"Kopparty, S., Saraf, S.: Local list-decoding and testing of sparse random linear codes from high-error, Technical report 115, Electronic Colloquium on Computational Complexity (ECCC) (2009)","DOI":"10.1145\/1806689.1806748"},{"key":"6_CR42","unstructured":"Kuhn, F.: Local multicoloring algorithms: computing a nearly-optimal TDMA schedule in constant time. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, pp. 613\u2013624 (2009)"},{"key":"6_CR43","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T.: Distributed approximation of capacitated dominating sets. In: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 161\u2013170 (2007)","DOI":"10.1145\/1248377.1248403"},{"key":"6_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/11561927_21","volume-title":"Distributed Computing","author":"F Kuhn","year":"2005","unstructured":"Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 273\u2013287. Springer, Heidelberg (2005). doi:10.1007\/11561927_21"},{"key":"6_CR45","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing, pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"6_CR46","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 980\u2013989 (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"6_CR47","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings of the 25th ACM Symposium on Principles of Distributed Computing, pp. 7\u201315 (2006)","DOI":"10.1145\/1146381.1146387"},{"key":"6_CR48","doi-asserted-by":"crossref","unstructured":"Levi, R., Moshkovitz, G., Ron, D., Rubinfeld, R., Shapira, A.: Constructing near spanning trees with few local inspections. Random Struct. Algorithms (2016)","DOI":"10.1002\/rsa.20652"},{"key":"6_CR49","unstructured":"Levi, R., Ron, D., Rubinfeld, R.: Local algorithms for sparse spanning graphs. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2014, 4\u20136 September 2014, Barcelona, pp. 826\u2013842 (2014)"},{"key":"6_CR50","unstructured":"Levi, R., Ron, D., Rubinfeld, R.: A local algorithm for constructing spanners in minor-free graphs. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2016, 7\u20139 September 2016, Paris, pp. 38:1\u201338:15 (2016)"},{"key":"6_CR51","doi-asserted-by":"crossref","unstructured":"Levi, R., Rubinfeld, R., Yodpinyanee, A.: Brief announcement: local computation algorithms for graphs of non-constant degrees. In: Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, 13\u201315 June 2015, pp. 59\u201361 (2015). http:\/\/doi.acm.org\/10.1145\/2755573.2755615","DOI":"10.1145\/2755573.2755615"},{"key":"6_CR52","unstructured":"Lipton, R.: New directions in testing. In: Proceedings of the DIMACS Workshop on Distributed Computing and Cryptography (1989)"},{"key":"6_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/978-3-642-31594-7_55","volume-title":"Automata, Languages, and Programming","author":"Y Mansour","year":"2012","unstructured":"Mansour, Y., Rubinstein, A., Vardi, S., Xie, N.: Converting online algorithms to local computation algorithms. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 653\u2013664. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-31594-7_55"},{"key":"6_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-40328-6_19","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Y Mansour","year":"2013","unstructured":"Mansour, Y., Vardi, S.: A local computation approximation scheme to maximum matching. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) APPROX\/RANDOM-2013. LNCS, vol. 8096, pp. 260\u2013273. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-40328-6_19"},{"key":"6_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/11830924_43","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S Marko","year":"2006","unstructured":"Marko, S., Ron, D.: Distance approximation in bounded-degree and general sparse graphs. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX\/RANDOM-2006. LNCS, vol. 4110, pp. 475\u2013486. Springer, Heidelberg (2006). doi:10.1007\/11830924_43"},{"key":"6_CR56","unstructured":"Mayer, A., Naor, S., Stockmeyer, L.: Local computations on static and dynamic graphs. In: Proceedings of the 3rd Israel Symposium on Theory and Computing Systems (1995)"},{"key":"6_CR57","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Strauss, M., Zheng, X.: Workload-optimal histograms on streams. Technical report 2005-19, DIMACS Technical Report (2005)","DOI":"10.1007\/11561071_65"},{"issue":"6","key":"6_CR58","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"key":"6_CR59","doi-asserted-by":"crossref","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 327\u2013336 (2008)","DOI":"10.1109\/FOCS.2008.81"},{"key":"6_CR60","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: 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), Kyoto, January 2012","DOI":"10.1137\/1.9781611973099.88"},{"key":"6_CR61","unstructured":"Orecchia, L., Allen Zhu, Z.: Flow-based algorithms for local graph clustering. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, 5\u20137 January 2014, pp. 1267\u20131286 (2014)"},{"issue":"1\u20133","key":"6_CR62","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\u20133), 183\u2013196 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR63","doi-asserted-by":"crossref","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. In: PODC, pp. 77\u201385 (1987)","DOI":"10.1145\/41840.41847"},{"issue":"3","key":"6_CR64","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00446-009-0091-7","volume":"22","author":"S Pettie","year":"2010","unstructured":"Pettie, S.: Distributed algorithms for ultrasparse spanners and linear size skeletons. Distrib. Comput. 22(3), 147\u2013166 (2010)","journal-title":"Distrib. Comput."},{"key":"6_CR65","unstructured":"Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: Proceedings of the Innovations in Computer Science Conference (2011)"},{"key":"6_CR66","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy bounds. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 1230\u20131239 (2006)","DOI":"10.1145\/1109557.1109693"},{"issue":"7","key":"6_CR67","doi-asserted-by":"publisher","first-page":"2897","DOI":"10.1137\/080728561","volume":"39","author":"ME Saks","year":"2010","unstructured":"Saks, M.E., Seshadhri, C.: Local monotonicity reconstruction. SIAM J. Comput. 39(7), 2897\u20132926 (2010)","journal-title":"SIAM J. Comput."},{"key":"6_CR68","doi-asserted-by":"crossref","unstructured":"Sarlos, T., Benczur, A., Csalogany, K., Fogaras, D., Racz, B.: To randomize or not to randomize: space optimal summaries for hyperlink analysis. In: Proceedings of the 15th International Conference on World Wide Web, pp. 297\u2013306 (2006)","DOI":"10.1145\/1135777.1135823"},{"key":"6_CR69","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A log-star distributed maximal independent set algorithm for growth-bounded graphs. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, pp. 35\u201344 (2008)","DOI":"10.1145\/1400751.1400758"},{"key":"6_CR70","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A new technique for distributed symmetry breaking. In: Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, pp. 257\u2013266 (2010)","DOI":"10.1145\/1835698.1835760"},{"key":"6_CR71","doi-asserted-by":"crossref","unstructured":"Spielman, D., Teng, S.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Proceedings of the 36th Annual ACM Symposium on the Theory of Computing, pp. 81\u201390 (2004)","DOI":"10.1145\/1007352.1007372"},{"issue":"2","key":"6_CR72","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci. 62(2), 236\u2013266 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"6_CR73","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1145\/1721654.1721674","volume":"53","author":"S Yekhanin","year":"2010","unstructured":"Yekhanin, S.: Private information retrieval. Commun. ACM 53(4), 68\u201373 (2010)","journal-title":"Commun. ACM"},{"key":"6_CR74","doi-asserted-by":"crossref","unstructured":"Yoshida, Y., Yamamoto, Y., Ito, H.: An improved constant-time approximation algorithm for maximum matchings. In: Proceedings of the 41st Annual ACM Symposium on the Theory of Computing, pp. 225\u2013234 (2009)","DOI":"10.1145\/1536414.1536447"},{"key":"6_CR75","unstructured":"Zhu, Z.A., Lattanzi, S., Mirrokni, V.: A local algorithm for finding well-connected clusters. In: Proceedings of the Thirtieth International Conference on Machine Learning (2013)"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-58747-9_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:47:08Z","timestamp":1750225628000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-58747-9_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319587462","9783319587479"],"references-count":75,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-58747-9_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"6 May 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kazan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/logic.pdmi.ras.ru\/csr2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}