{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T12:04:56Z","timestamp":1773230696103,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642392054","type":"print"},{"value":"9783642392061","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_46","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"540-551","source":"Crossref","is-referenced-by-count":14,"title":["Local Correctability of Expander Codes"],"prefix":"10.1007","author":[{"given":"Brett","family":"Hemenway","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mary","family":"Wootters","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"46_CR1","unstructured":"Assmus, E.F., Key, J.D.: Designs and their Codes, vol. 103. Cambridge University Press (1994)"},{"key":"46_CR2","unstructured":"Assmus, E.F., Key, J.D.: Polynomial codes and finite geometries. In: Handbook of Coding Theory, vol.\u00a02(part 2), pp. 1269\u20131343 (1998)"},{"key":"46_CR3","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/103418.103428","volume-title":"Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 21\u201332. ACM, New York (1991)"},{"issue":"6","key":"46_CR4","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1109\/TIT.2002.1003853","volume":"48","author":"A. Barg","year":"2002","unstructured":"Barg, A., Zemor, G.: Error exponents of expander codes. IEEE Transactions on Information Theory\u00a048(6), 1725\u20131729 (2002)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"46_CR5","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.1109\/TIT.2005.846392","volume":"51","author":"A. Barg","year":"2005","unstructured":"Barg, A., Zemor, G.: Concatenated codes: serial and parallel. IEEE Trans. Inf. Theor.\u00a051(5), 1625\u20131634 (2005)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"1","key":"46_CR6","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1109\/TIT.2005.860415","volume":"52","author":"A. Barg","year":"2006","unstructured":"Barg, A., Zemor, G.: Distance properties of expander codes. IEEE Transactions on Information Theory\u00a052(1), 78\u201390 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"key":"46_CR7","first-page":"258","volume-title":"CCC 2012","author":"A. Beimel","year":"2012","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., Orlov, I.: Share Conversion and Private Information Retrieval. In: CCC 2012, pp. 258\u2013268. IEEE Computer Society, Los Alamitos (2012)"},{"key":"46_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Aroya, A., Efremenko, K., Ta-Shma, A.: Local List Decoding with a Constant Number of Queries. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 715\u2013722. IEEE (October 2010)","DOI":"10.1109\/FOCS.2010.88"},{"key":"46_CR9","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1145\/100216.100225","volume-title":"Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990","author":"M. Blum","year":"1990","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990, pp. 73\u201383. ACM, New York (1990)"},{"issue":"3","key":"46_CR10","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. Journal of Computer and System Sciences\u00a047(3), 549\u2013595 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"46_CR11","doi-asserted-by":"crossref","unstructured":"Chee, Y.M., Feng, T., Ling, S., Wang, H., Zhang, L.F.: Query-Efficient Locally Decodable Codes of Subexponential Length. In: Computational Complexity, pp. 1\u201331 (August 2011)","DOI":"10.1007\/s00037-011-0017-1"},{"issue":"4","key":"46_CR12","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1137\/100804322","volume":"40","author":"Z. Dvir","year":"2011","unstructured":"Dvir, Z., Gopalan, P., Yekhanin, S.: Matching Vector Codes. SIAM Journal on Computing\u00a040(4), 1154\u20131178 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"46_CR13","doi-asserted-by":"crossref","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. In: STOC 2009, pp. 39\u201344. ACM (2009)","DOI":"10.1145\/1536414.1536422"},{"key":"46_CR14","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1145\/2213977.2214008","volume-title":"Proceedings of the 44th Symposium on Theory of Computing, STOC 2012","author":"K. Efremenko","year":"2012","unstructured":"Efremenko, K.: From irreducible representations to locally decodable codes. In: Proceedings of the 44th Symposium on Theory of Computing, STOC 2012, pp. 327\u2013338. ACM, New York (2012)"},{"key":"46_CR15","doi-asserted-by":"crossref","unstructured":"Gallager, R.G.: Low Density Parity-Check Codes. Technical report. MIT (1963)","DOI":"10.7551\/mitpress\/4347.001.0001"},{"key":"46_CR16","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/103418.103429","volume-title":"Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991","author":"P. Gemmell","year":"1991","unstructured":"Gemmell, P., Lipton, R.J., Rubinfeld, R., Sudan, M., Wigderson, A.: Self-testing\/correcting for polynomials and for approximate functions. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 33\u201342. ACM, New York (1991)"},{"issue":"4","key":"46_CR17","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(92)90195-2","volume":"43","author":"P. Gemmell","year":"1992","unstructured":"Gemmell, P., Sudan, M.: Highly resilient correctors for polynomials. Information Processing Letters\u00a043(4), 169\u2013174 (1992)","journal-title":"Information Processing Letters"},{"key":"46_CR18","doi-asserted-by":"crossref","unstructured":"Guo, A., Kopparty, S., Sudan, M.: New affine-invariant codes from lifting. In: ITCS (2013)","DOI":"10.1145\/2422436.2422494"},{"issue":"4","key":"46_CR19","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bulletin of the American Mathematical Society\u00a043(4), 439\u2013562 (2006)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"46_CR20","doi-asserted-by":"crossref","unstructured":"Itoh, T., Suzuki, Y.: New Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length. IEICE Transactions on Information and Systems\u00a0E93-D(2), 263\u2013270 (2010)","DOI":"10.1587\/transinf.E93.D.263"},{"key":"46_CR21","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: STOC 2000: Proceedings of the 32nd Annual Symposium on the Theory of Computing, pp. 80\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"key":"46_CR22","doi-asserted-by":"crossref","unstructured":"Kopparty, S., Saraf, S., Yekhanin, S.: High-rate codes with sublinear-time decoding. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 167\u2013176. ACM (2011)","DOI":"10.1145\/1993636.1993660"},{"key":"46_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/3-540-52282-4_44","volume-title":"STACS 90","author":"R.J. Lipton","year":"1990","unstructured":"Lipton, R.J.: Efficient checking of computations. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol.\u00a0415, pp. 207\u2013215. Springer, Heidelberg (1990)"},{"issue":"3","key":"46_CR24","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica\u00a08(3), 261\u2013277 (1988)","journal-title":"Combinatorica"},{"issue":"1","key":"46_CR25","first-page":"39","volume":"9","author":"G.A. Margulis","year":"1988","unstructured":"Margulis, G.A.: Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problems of Information Transmission\u00a09(1), 39\u201346 (1988)","journal-title":"Problems of Information Transmission"},{"issue":"1","key":"46_CR26","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1006\/jctb.1994.1054","volume":"62","author":"M. Morgenstern","year":"1994","unstructured":"Morgenstern, M.: Existence and explicit constructions of q\u2009+\u20091 regular ramanujan graphs for every prime power q. Journal of Combinatorial Theory, Series B\u00a062(1), 44\u201362 (1994)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"46_CR27","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1145\/195058.195132","volume-title":"Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC 1994","author":"A. Polishchuk","year":"1994","unstructured":"Polishchuk, A., Spielman, D.A.: Nearly-linear size holographic proofs. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC 1994, pp. 194\u2013203. ACM, New York (1994)"},{"issue":"4","key":"46_CR28","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1109\/TIT.1954.1057465","volume":"4","author":"I. Reed","year":"1954","unstructured":"Reed, I.: A class of multiple-error-correcting codes and the decoding scheme. Transactions of the IRE Professional Group on Information Theory\u00a04(4), 38\u201349 (1954)","journal-title":"Transactions of the IRE Professional Group on Information Theory"},{"issue":"6","key":"46_CR29","doi-asserted-by":"publisher","first-page":"1710","DOI":"10.1109\/18.556667","volume":"42","author":"M. Sipser","year":"1996","unstructured":"Sipser, M., Spielman, D.A.: Expander codes. IEEE Transactions on Information Theory\u00a042(6), 1710\u20131722 (1996)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"46_CR30","doi-asserted-by":"publisher","first-page":"1723","DOI":"10.1109\/18.556668","volume":"42","author":"D.A. Spielman","year":"1996","unstructured":"Spielman, D.A.: Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory\u00a042(6), 1723\u20131731 (1996)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"46_CR31","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1109\/TIT.1981.1056404","volume":"27","author":"R. Tanner","year":"1981","unstructured":"Tanner, R.: A recursive approach to low complexity codes. IEEE Transactions on Information Theory\u00a027(5), 533\u2013547 (1981)","journal-title":"IEEE Transactions on Information Theory"},{"key":"46_CR32","doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. J. ACM\u00a055(1) (2008)","DOI":"10.1145\/1326554.1326555"},{"key":"46_CR33","doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Locally Decodable Codes. Foundations and Trends in Theoretical Computer Science (2010)","DOI":"10.1007\/978-3-642-20712-9_22"},{"issue":"2","key":"46_CR34","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1109\/18.910593","volume":"47","author":"G. Zemor","year":"2001","unstructured":"Zemor, G.: On expander codes. IEEE Transactions on Information Theory\u00a047(2), 835\u2013837 (2001)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_46","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:07:28Z","timestamp":1557911248000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}