{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T13:40:02Z","timestamp":1740577202148,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":66,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642163661"},{"type":"electronic","value":"9783642163678"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16367-8_6","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T15:25:55Z","timestamp":1286465155000},"page":"65-104","source":"Crossref","is-referenced-by-count":12,"title":["Short Locally Testable Codes and Proofs: A Survey in Two Parts"],"prefix":"10.1007","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/978-3-540-45198-3_17","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"N. Alon","year":"2003","unstructured":"Alon, N., Krivelevich, M., Kaufman, T., Litsyn, S., Ron, D.: Testing low-degree polynomials over GF(2). In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 188\u2013199. Springer, Heidelberg (2003)"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/3-540-63165-8_196","volume-title":"Automata, Languages and Programming","author":"A. Ambainis","year":"1997","unstructured":"Ambainis, A.: An upper bound on the communication complexity of private information retrieval. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 401\u2013407. Springer, Heidelberg (1997)"},{"unstructured":"Arora, S.: Probabilistic checking of proofs and the hardness of approximation problems. PhD thesis, UC Berkeley (1994)","key":"6_CR3"},{"issue":"3","key":"6_CR4","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the ACM\u00a045(3), 501\u2013555 (1998); Preliminary Version in 33rd FOCS (1992)","journal-title":"Journal of the ACM"},{"issue":"1","key":"6_CR5","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of\u00a0NP. Journal of the ACM\u00a045(1), 70\u2013122 (1998); Preliminary Version in 33rd FOCS (1992)","journal-title":"Journal of the ACM"},{"issue":"1","key":"6_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity\u00a01(1), 3\u201340 (1991)","journal-title":"Computational Complexity"},{"doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proc. 23rd ACM Symposium on the Theory of Computing, pp. 21\u201331 (May 1991)","key":"6_CR7","DOI":"10.1145\/103418.103428"},{"doi-asserted-by":"crossref","unstructured":"Barak, B.: How to go beyond the black-box simulation barrier. In: Proc. 42nd IEEE Symposium on Foundations of Computer Science, pp. 106\u2013115 (October 2001)","key":"6_CR8","DOI":"10.1109\/SFCS.2001.959885"},{"doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., Raymond, J.F.: Breaking the O(n 1\/(2k\u2009\u2212\u20091)) barrier for information-theoretic private information retrieval. In: Proc. 43rd IEEE Symposium on Foundations of Computer Science, pp. 261\u2013270 (November 2002)","key":"6_CR9","DOI":"10.1109\/SFCS.2002.1181949"},{"doi-asserted-by":"crossref","unstructured":"Bellare, M., Coppersmith, D., H\u00e5stad, J., Kiwi, M., Sudan, M.: Linearity testing in characteristic two. In: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, pp. 432\u2013441 (1995)","key":"6_CR10","DOI":"10.1109\/SFCS.1995.492574"},{"issue":"3","key":"6_CR11","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs, and nonapproximability\u2014towards tight results. SIAM Journal on Computing\u00a027(3), 804\u2013915 (1998); Preliminary Version in 36th FOCS (1995)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximation. In: Proc. 25th ACM Symposium on the Theory of Computing, pp. 294\u2013304 (May 1993)","key":"6_CR12","DOI":"10.1145\/167088.167174"},{"doi-asserted-by":"crossref","unstructured":"Bellare, M., Sudan, M.: Improved non-approximability results. In: Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, pp. 184\u2013193 (1994)","key":"6_CR13","DOI":"10.1145\/195058.195129"},{"key":"6_CR14","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)"},{"doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Robust PCPs of proximity, shorter PCPs and applications to coding. In: Proc. 36th ACM Symposium on the Theory of Computing, pp. 1???10 (June 2004);","key":"#cr-split#-6_CR15.1","DOI":"10.1145\/1007352.1007361"},{"doi-asserted-by":"crossref","unstructured":"See ECCC Technical Report TR04-021 (March 2004)","key":"#cr-split#-6_CR15.2","DOI":"10.1088\/1126-6708\/2004\/08\/021"},{"doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Short PCPs verifiable in polylogarithmic time. In: 20th IEEE Conference on Computational Complexity, pp. 120\u2013134 (2005)","key":"6_CR16","DOI":"10.1109\/CCC.2005.27"},{"doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Guruswami, V., Kaufman, T., Sudan, M., Viderman, M.: Locally testable codes require redundant testers. In: 24th IEEE Conference on Computational Complexity, pp. 52\u201361 (2009)","key":"6_CR17","DOI":"10.1109\/CCC.2009.6"},{"doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF properties are hard to test. In: Proc. 35th ACM Symposium on the Theory of Computing, pp. 345\u2013354 (June 2003)","key":"6_CR18","DOI":"10.1145\/780542.780594"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/978-3-540-27821-4_26","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E. Ben-Sasson","year":"2004","unstructured":"Ben-Sasson, E., Sudan, M.: Robust locally testable codes and products of codes. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 286\u2013297. Springer, Heidelberg (2004); See ECCC TR04-046 (2004)"},{"issue":"2","key":"6_CR20","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/050646445","volume":"38","author":"E. Ben-Sasson","year":"2008","unstructured":"Ben-Sasson, E., Sudan, M.: Short PCPs with polylog query complexity. SIAM Journal on Computing\u00a038(2), 551\u2013607 (2008); Preliminary Version in 37th STOC (2005)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M., Vadhan, S., Wigderson, A.: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In: Proc. 35th ACM Symposium on the Theory of Computing, pp. 612\u2013621 (June 2003)","key":"6_CR21","DOI":"10.1145\/780542.780631"},{"issue":"3","key":"6_CR22","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 Science\u00a047(3), 549\u2013595 (1993); Preliminary Version in 22nd STOC (1990)","journal-title":"Journal of Computer and System Science"},{"unstructured":"Buhrman, H., de Wolf, R.: On relaxed locally decodable codes (July 2004) (unpublished manuscript)","key":"6_CR23"},{"doi-asserted-by":"crossref","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. In: Proc. 30th ACM Symposium on the Theory of Computing, pp. 209\u2013218 (May 1998)","key":"6_CR24","DOI":"10.1145\/276698.276741"},{"issue":"6","key":"6_CR25","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B. Chor","year":"1998","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. Journal of the ACM\u00a045(6), 965\u2013982 (1998)","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Dinur, I.: The PCP theorem by gap amplification. Journal of the ACM??54(3), Art. 12 (2007);","key":"#cr-split#-6_CR26.1","DOI":"10.1145\/1236457.1236459"},{"unstructured":"Extended abstract in 38th STOC (2006)","key":"#cr-split#-6_CR26.2"},{"key":"6_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-642-16367-8_21","volume-title":"Property Testing","author":"I. Dinur","year":"2010","unstructured":"Dinur, I., Harsha, P.: Composition of low-error 2-query PCPs using decodable PCPs. In: Goldreich, O. (ed.) Property Testing. LNCS, vol.\u00a06390, pp. 65\u2013104. Springer, Heidelberg (2010)"},{"issue":"4","key":"6_CR28","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1137\/S0097539705446962","volume":"36","author":"I. Dinur","year":"2006","unstructured":"Dinur, I., Reingold, O.: Assignment-testers: Towards a combinatorial proof of the PCP-Theorem. SIAM Journal on Computing\u00a036(4), 975\u20131024 (2006); Extended abstract in 45th FOCS (2004)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. In: 41st ACM Symposium on the Theory of Computing, pp. 39\u201344 (2009)","key":"6_CR29","DOI":"10.1145\/1536414.1536422"},{"doi-asserted-by":"crossref","unstructured":"Erg\u00fcn, F., Kumar, R., Rubinfeld, R.: Fast approximate PCPs. In: Proc. 31st ACM Symposium on the Theory of Computing, pp. 41\u201350 (May 1999)","key":"6_CR30","DOI":"10.1145\/301250.301267"},{"issue":"2","key":"6_CR31","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. Journal of the ACM\u00a043(2), 268\u2013292 (1996); Preliminary version in 32nd FOCS (1991)","journal-title":"Journal of the ACM"},{"key":"6_CR32","volume-title":"Concatenated Codes","author":"G.D. Forney","year":"1966","unstructured":"Forney, G.D.: Concatenated Codes. MIT Press, Cambridge (1966)"},{"issue":"2","key":"6_CR33","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/0304-3975(94)90251-8","volume":"134","author":"L. Fortnow","year":"1994","unstructured":"Fortnow, L., Rompel, J., Sipser, M.: On the power of multi-prover interactive protocols. Theoretical Computer Science\u00a0134(2), 545\u2013557 (1994)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Friedl, K., Sudan, M.: Some improvements to total degree tests. In: Proc. 3rd Israel Symposium on Theoretical and Computing Systems, Tel Aviv, Israel, January 4-6, pp. 190\u2013198 (1995)","key":"6_CR34","DOI":"10.1109\/ISTCS.1995.377032"},{"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: Proc. 23rd ACM Symposium on the Theory of Computing, pp. 32\u201342 (1991)","key":"6_CR35","DOI":"10.1145\/103418.103429"},{"unstructured":"Goldreich, O.: Short locally testable codes and proofs (survey). ECCC Technical Report TR05-014 (January 2005)","key":"6_CR36"},{"key":"6_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational Complexity: A Conceptual Perspective","author":"O. Goldreich","year":"2008","unstructured":"Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge (2008)"},{"issue":"4","key":"6_CR38","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM\u00a045(4), 653\u2013750 (1998); Preliminary Version in 37th FOCS (1996)","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: On proximity oblivious testing. ECCC, TR08-041 (2008);","key":"#cr-split#-6_CR39.1","DOI":"10.1145\/1536414.1536436"},{"unstructured":"Also in the proceedings of the 41st STOC (2009)","key":"#cr-split#-6_CR39.2"},{"doi-asserted-by":"crossref","unstructured":"Goldreich, O., Karloff, H., Schulman, L., Trevisan, L.: Lower bounds for linear locally decodable codes and private information retrieval. In: Proc. 17th Conference on Computational Complexity, Montr\u00e9al, Qu\u00e9bec, Canada, May 21-24, pp. 175\u2013183 (2002)","key":"6_CR40","DOI":"10.1109\/CCC.2002.1004353"},{"doi-asserted-by":"crossref","unstructured":"Goldreich, O., Sudan, M.: Locally testable codes and PCPs of almost linear length. In: Proc. 43rd IEEE Symposium on Foundations of Computer Science, pp. 13???22 (November 2002);","key":"#cr-split#-6_CR41.1","DOI":"10.1109\/SFCS.2002.1181878"},{"doi-asserted-by":"crossref","unstructured":"See ECCC Report TR02-050 (2002)","key":"#cr-split#-6_CR41.2","DOI":"10.1088\/1126-6708\/2002\/10\/050"},{"issue":"3-4","key":"6_CR42","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/PL00001606","volume":"9","author":"P. Harsha","year":"2000","unstructured":"Harsha, P., Sudan, M.: Small PCPs with low query complexity. Computational Complexity\u00a09(3-4), 157\u2013201 (2000); Preliminary Version in 18th STACS (2001)","journal-title":"Computational Complexity"},{"key":"6_CR43","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n 1\u2009\u2212\u2009\u03b5 . Acta Mathematica\u00a0182, 105\u2013142 (1999); Preliminary Versions in 28th STOC (1996), and 37th FOCS (1997)","journal-title":"Acta Mathematica"},{"issue":"4","key":"6_CR44","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048(4), 798\u2013859 (2001); Preliminary Version in 29th STOC (1997)","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: Proc. 32nd ACM Symposium on the Theory of Computing, pp. 80\u201386 (2000)","key":"6_CR45","DOI":"10.1145\/335305.335315"},{"issue":"5","key":"6_CR46","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1137\/080715548","volume":"39","author":"T. Kaufman","year":"2009","unstructured":"Kaufman, T., Litsyn, S., Xie, N.: Breaking the \u03b5-soundness bound of the linearity test over GF(2). SIAM Journal on Computing\u00a039(5), 1988\u20132003 (2009)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes via a quantum argument. In: Proc. 35th ACM Symposium on the Theory of Computing, pp. 106\u2013115 (June 2003)","key":"6_CR47","DOI":"10.1145\/780542.780560"},{"doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Proc. 24th ACM Symposium on the Theory of Computing, pp. 723\u2013732 (May 1992)","key":"6_CR48","DOI":"10.1145\/129712.129782"},{"doi-asserted-by":"crossref","unstructured":"Lapidot, D., Shamir, A.: Fully parallelized multi prover protocols for NEXP-time. In: Proc. 32nd IEEE Symposium on Foundations of Computer Science, pp. 13\u201318 (October 1991) (extended abstract)","key":"6_CR49","DOI":"10.1109\/SFCS.1991.185342"},{"issue":"4","key":"6_CR50","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. Journal of the ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"Journal of the ACM"},{"issue":"2","key":"6_CR51","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1137\/080729967","volume":"39","author":"O. Meir","year":"2009","unstructured":"Meir, O.: Combinatorial construction of locally testable codes. SIAM Journal on Computing\u00a039(2), 491\u2013544 (2009); Extended abstrat in 40th STOC (2008)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Meir, O.: Combinatorial PCPs with efficient verifiers. In: 50th IEEE Symposium on Foundations of Computer Science, pp. 463\u2013471 (2009)","key":"6_CR52","DOI":"10.1109\/FOCS.2009.10"},{"issue":"4","key":"6_CR53","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S. Micali","year":"2000","unstructured":"Micali, S.: Computationally sound proofs. SIAM Journal on Computing\u00a030(4), 1253\u20131298 (2000); Preliminary Version in 35th FOCS (1994)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Moshkovitz, D., Raz, R.: Two query PCP with sub-constant error. In: 49th IEEE Symposium on Foundations of Computer Science, pp. 314\u2013323 (2008)","key":"6_CR54","DOI":"10.1109\/FOCS.2008.60"},{"doi-asserted-by":"crossref","unstructured":"Polishchuk, A., Spielman, D.A.: Nearly-linear size holographic proofs. In: Proc. 26th ACM Symposium on the Theory of Computing, pp. 194\u2013203 (May 1994)","key":"6_CR55","DOI":"10.1145\/195058.195132"},{"issue":"3","key":"6_CR56","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM Journal of Computing\u00a027(3), 763\u2013803 (1998); Preliminary Version in 27th STOC (1995)","journal-title":"SIAM Journal of Computing"},{"issue":"2","key":"6_CR57","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing\u00a025(2), 252\u2013271 (1996); Preliminary Version in 3rd SODA (1992)","journal-title":"SIAM Journal on Computing"},{"unstructured":"Spielman, D.: Computationally efficient error-correcting codes and holographic proofs. PhD thesis, Massachusetts Institute of Technology (June 1995)","key":"6_CR58"},{"unstructured":"Sudan, M.: Efficient checking of polynomials and proofs and the hardness of approximation problems. Ph.D.??Thesis, Computer Science Division, University of California at Berkeley (1992);","key":"#cr-split#-6_CR59.1"},{"unstructured":"Also appears as Lecture Notes in Computer Science, Vol. 1001, Springer (1996)","key":"#cr-split#-6_CR59.2"},{"key":"6_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1007\/3-540-48523-6_64","volume-title":"Automata, Languages and Programming","author":"M. Szegedy","year":"1999","unstructured":"Szegedy, M.: Many-valued logics and holographic proofs. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, pp. 676\u2013686. Springer, Heidelberg (1999)"},{"doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Towards 3-Query locally decodable codes of subexponential length. In: 39th ACM Symposium on the Theory of Computing, pp. 266\u2013274 (2007)","key":"6_CR61","DOI":"10.1145\/1250790.1250830"}],"container-title":["Lecture Notes in Computer Science","Property Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16367-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T13:18:29Z","timestamp":1740575909000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":66,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}