{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:29Z","timestamp":1763468009529},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_50","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"670-682","source":"Crossref","is-referenced-by-count":9,"title":["Locally Testable vs. Locally Decodable Codes"],"prefix":"10.1007","author":[{"given":"Tali","family":"Kaufman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Viderman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"50_CR1","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1109\/SFCS.2003.1238186","volume-title":"Proceedings: 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003","author":"L. Babai","year":"2003","unstructured":"Babai, L., Shpilka, A., Stefankovic, D.: Locally testable cyclic codes. In: IEEE (ed.) Proceedings: 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, Cambridge, Massachusetts, October 11-14, pp. 116\u2013125. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"50_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/978-3-540-45198-3_19","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E. Ben-Sasson","year":"2003","unstructured":"Ben-Sasson, E., Goldreich, O., Sudan, M.: Bounds on 2-query codeword testing. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 216\u2013227. Springer, Heidelberg (2003)"},{"key":"50_CR3","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1109\/CCC.2009.6","volume-title":"IEEE Conference on Computational Complexity","author":"E. Ben-Sasson","year":"2009","unstructured":"Ben-Sasson, E., Guruswami, V., Kaufman, T., Sudan, M., Viderman, M.: Locally testable codes require redundant testers. In: IEEE Conference on Computational Complexity, pp. 52\u201361. IEEE Computer Society, Los Alamitos (2009)"},{"issue":"1","key":"50_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E. Ben-Sasson","year":"2005","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF properties are hard to test. SIAM Journal on Computing\u00a035(1), 1\u201321 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"50_CR5","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1145\/1060590.1060631","volume-title":"STOC","author":"E. Ben-Sasson","year":"2005","unstructured":"Ben-Sasson, E., Sudan, M.: Simple PCPs with poly-log rate and query complexity. In: STOC, pp. 266\u2013275. ACM, New York (2005)"},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. JACM: Journal of the ACM\u00a045 (1998)","DOI":"10.1145\/293347.293350"},{"issue":"3","key":"50_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I. Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. Journal of the ACM\u00a054(3), 12:1\u201312:44 (2007)","journal-title":"Journal of the ACM"},{"issue":"5","key":"50_CR8","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1137\/05063605X","volume":"36","author":"Z. Dvir","year":"2007","unstructured":"Dvir, Z., Shpilka, A.: Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput.\u00a036(5), 1404\u20131434 (2007)","journal-title":"SIAM J. Comput."},{"key":"50_CR9","first-page":"39","volume-title":"STOC","author":"K. Efremenko","year":"2009","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. In: Mitzenmacher, M. (ed.) STOC, pp. 39\u201344. ACM, New York (2009)"},{"key":"50_CR10","unstructured":"Goldreich, O.: Short locally testable codes and proofs (survey). Electronic Colloquium on Computational Complexity (ECCC)\u00a0(014) (2005)"},{"issue":"3","key":"50_CR11","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00037-006-0216-3","volume":"15","author":"O. Goldreich","year":"2006","unstructured":"Goldreich, O., Karloff, H.J., Schulman, L.J., Trevisan, L.: Lower bounds for linear locally decodable codes and private information retrieval. Computational Complexity\u00a015(3), 263\u2013296 (2006)","journal-title":"Computational Complexity"},{"issue":"4","key":"50_CR12","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/1162349.1162351","volume":"53","author":"O. Goldreich","year":"2006","unstructured":"Goldreich, O., Sudan, M.: Locally testable codes and PCPs of almost-linear length. Journal of the ACM\u00a053(4), 558\u2013655 (2006)","journal-title":"Journal of the ACM"},{"key":"50_CR13","unstructured":"Gopalan, P.: A note on efremenko\u2019s locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC)\u00a0(069) (2009)"},{"key":"50_CR14","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1109\/CCC.2008.31","volume-title":"IEEE Conference on Computational Complexity","author":"E. Grigorescu","year":"2008","unstructured":"Grigorescu, E., Kaufman, T., Sudan, M.: 2-transitivity is insufficient for local testability. In: IEEE Conference on Computational Complexity, pp. 259\u2013267. IEEE Computer Society, Los Alamitos (2008)"},{"key":"50_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/11940128_28","volume-title":"Algorithms and Computation","author":"V. Guruswami","year":"2006","unstructured":"Guruswami, V.: On 2-query codeword testing with near-perfect completeness. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 267\u2013276. Springer, Heidelberg (2006)"},{"key":"50_CR16","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: STOC, pp. 80\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"key":"50_CR17","first-page":"590","volume-title":"FOCS","author":"T. Kaufman","year":"2007","unstructured":"Kaufman, T., Sudan, M.: Sparse random linear codes are locally decodable and testable. In: FOCS, pp. 590\u2013600. IEEE Computer Society, Los Alamitos (2007)"},{"key":"50_CR18","first-page":"403","volume-title":"STOC","author":"T. Kaufman","year":"2008","unstructured":"Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: STOC, pp. 403\u2013412. ACM, New York (2008)"},{"key":"50_CR19","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Wigderson, A.: Symmetric ldpc and local testing. In: ICS (2010)","DOI":"10.1007\/978-3-642-16367-8_25"},{"key":"50_CR20","doi-asserted-by":"crossref","unstructured":"Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC)\u00a0(059) (2002)","DOI":"10.1145\/780542.780560"},{"key":"50_CR21","first-page":"285","volume-title":"STOC","author":"O. Meir","year":"2008","unstructured":"Meir, O.: Combinatorial construction of locally testable codes. In: STOC, pp. 285\u2013294. ACM, New York (2008)"},{"key":"50_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/3-540-45726-7_4","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"K. Obata","year":"2002","unstructured":"Obata, K.: Optimal lower bounds for 2-query locally decodable linear codes. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 39\u201350. Springer, Heidelberg (2002)"},{"key":"50_CR23","doi-asserted-by":"crossref","unstructured":"Shiowattana, Lokam: An optimal lower bound for 2-query locally decodable linear codes. IPL: Information Processing Letters\u00a097 (2006)","DOI":"10.1016\/j.ipl.2005.11.009"},{"key":"50_CR24","unstructured":"Trevisan, L.: Some applications of coding theory in computational complexity, September 23 (2004)"},{"key":"50_CR25","unstructured":"Woodruff: New lower bounds for general locally decodable codes. ECCC: Electronic Colloquium on Computational Complexity, technical reports (2007)"},{"key":"50_CR26","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"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T01:04:36Z","timestamp":1685754276000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}