{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:19:10Z","timestamp":1725567550834},"publisher-location":"Berlin, Heidelberg","reference-count":53,"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_3","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T15:25:55Z","timestamp":1286465155000},"page":"13-31","source":"Crossref","is-referenced-by-count":3,"title":["Limitation on the Rate of Families of Locally Testable Codes"],"prefix":"10.1007","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"3_CR1","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)","journal-title":"Journal of the ACM"},{"issue":"3","key":"3_CR2","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)","journal-title":"Journal of the ACM"},{"issue":"3","key":"3_CR3","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":"4","key":"3_CR4","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. J. ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"3_CR5","unstructured":"Goldreich, O.: Short locally testable codes and proofs (survey). Electronic Colloquium on Computational Complexity (ECCC) (014) (2005)"},{"key":"3_CR6","first-page":"347","volume":"13","author":"L. Trevisan","year":"2004","unstructured":"Trevisan, L.: Some applications of coding theory in computational complexity. Quaderni di Matematica\u00a013, 347\u2013424 (2004)","journal-title":"Quaderni di Matematica"},{"key":"3_CR7","volume-title":"The theory of error-correcting codes","author":"F. MacWilliams","year":"1978","unstructured":"MacWilliams, F., Sloane, N.: The theory of error-correcting codes. North-Holland, Amsterdam (1978)"},{"key":"3_CR8","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)"},{"issue":"8","key":"3_CR9","doi-asserted-by":"publisher","first-page":"2849","DOI":"10.1109\/TIT.2005.851735","volume":"51","author":"L. Babai","year":"2005","unstructured":"Babai, L., Shpilka, A., Stefankovic, D.: Locally testable cyclic codes. IEEE Transactions on Information Theory\u00a051(8), 2849\u20132858 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1109\/CCC.2009.6","volume-title":"CCC 2009: Proceedings of the 2009 24th Annual 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: CCC 2009: Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, Washington, DC, USA, pp. 52\u201361. IEEE Computer Society, Los Alamitos (2009)"},{"issue":"3","key":"3_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)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR12","unstructured":"Meir, O.: On the efficiency of non-uniform pcpp verifiers. Electronic Colloquium on Computational Complexity (ECCC)\u00a015(064) (2008)"},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1145\/100216.100225","volume-title":"STOC","author":"M. Blum","year":"1990","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. In: STOC, pp. 73\u201383. ACM, New York (1990)"},{"issue":"6","key":"3_CR14","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1109\/18.556674","volume":"42","author":"M. Bellare","year":"1996","unstructured":"Bellare, M., Coppersmith, D., Hastad, J., Kiwi, M., Sudan, M.: Linearity testing in characteristic two. IEEE Transactions on Information Theory\u00a042(6), 1781\u20131795 (1996)","journal-title":"IEEE Transactions on Information Theory"},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/103418.103428","volume-title":"Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Levin, L., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, pp. 21\u201332. ACM, New York (1991)"},{"key":"3_CR16","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1145\/258533.258641","volume-title":"Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing","author":"R. Raz","year":"1997","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, pp. 475\u2013484. ACM, New York (1997)"},{"issue":"3","key":"3_CR17","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\u00a023(3), 365\u2013426 (2003)","journal-title":"Combinatorica"},{"issue":"11","key":"3_CR18","doi-asserted-by":"publisher","first-page":"4032","DOI":"10.1109\/TIT.2005.856958","volume":"51","author":"N. Alon","year":"2005","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.: Testing reed-muller codes. IEEE Transactions on Information Theory\u00a051(11), 4032\u20134039 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"3_CR19","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1137\/S0097539704445615","volume":"36","author":"T. Kaufman","year":"2006","unstructured":"Kaufman, T., Ron, D.: Testing polynomials over general fields. SIAM J. Comput.\u00a036(3), 779\u2013802 (2006)","journal-title":"SIAM J. Comput."},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1145\/1250790.1250864","volume-title":"STOC","author":"A. Samorodnitsky","year":"2007","unstructured":"Samorodnitsky, A.: Low-degree tests at large distances. In: Johnson, D.S., Feige, U. (eds.) STOC, pp. 506\u2013515. ACM, New York (2007)"},{"key":"3_CR21","first-page":"403","volume-title":"STOC","author":"T. Kaufman","year":"2008","unstructured":"Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: Ladner, R.E., Dwork, C. (eds.) STOC, pp. 403\u2013412. ACM, New York (2008)"},{"key":"3_CR22","first-page":"259","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":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1007\/978-3-642-03685-9_40","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E. Grigorescu","year":"2009","unstructured":"Grigorescu, E., Kaufman, T., Sudan, M.: Succinct representation of codes with applications to testing. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX\u2013RANDOM 2009. LNCS, vol.\u00a05687, pp. 534\u2013547. Springer, Heidelberg (2009)"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M.: Limits on the rate of locally testable affine-invariant codes. Electronic Colloquium on Computational Complexity (ECCC)\u00a0(108) (2010)","DOI":"10.1007\/978-3-642-22935-0_35"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Sudan, M.: Invariance in Property Testing. ECCC, TR10-051 (2010)","DOI":"10.1007\/978-3-642-16367-8_12"},{"issue":"4","key":"3_CR26","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"E. Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput.\u00a036(4), 889\u2013974 (2006)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"3_CR27","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 J. Comput.\u00a036(4), 975\u20131024 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"3_CR28","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 J. Comput.\u00a039(2), 491\u2013544 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"3_CR29","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1002\/rsa.20120","volume":"28","author":"E. Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Sudan, M.: Robust locally testable codes and products of codes. Random Struct. Algorithms\u00a028(4), 387\u2013402 (2006)","journal-title":"Random Struct. Algorithms"},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D., Raz, R.: Two-query pcp with subconstant error. J. ACM\u00a057(5) (2010)","DOI":"10.1145\/1754399.1754402"},{"key":"3_CR31","first-page":"472","volume-title":"FOCS","author":"I. Dinur","year":"2009","unstructured":"Dinur, I., Harsha, P.: Composition of low-error 2-query pcps using decodable pcps. In: FOCS, pp. 472\u2013481. IEEE Computer Society, Los Alamitos (2009)"},{"key":"3_CR32","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":"3_CR33","first-page":"417","volume-title":"STOC","author":"S. Kopparty","year":"2010","unstructured":"Kopparty, S., Saraf, S.: Local list-decoding and testing of random linear codes from high error. In: Schulman, L.J. (ed.) STOC, pp. 417\u2013426. ACM, New York (2010)"},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Viderman, M.: Low rate is insufficient for local testability. In: Shaltiel, R. (ed.) Proc. 14th Intl. Workshop on Randomization and Computation - RANDOM 2010 (September 2010)","DOI":"10.1007\/978-3-642-15369-3_32"},{"key":"3_CR35","first-page":"723","volume-title":"STOC","author":"J. Kilian","year":"1992","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: STOC, pp. 723\u2013732. ACM, New York (1992)"},{"issue":"4","key":"3_CR36","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 J. Comput.\u00a030(4), 1253\u20131298 (2000)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"3_CR37","doi-asserted-by":"publisher","first-page":"1661","DOI":"10.1137\/070709244","volume":"38","author":"B. Barak","year":"2008","unstructured":"Barak, B., Goldreich, O.: Universal arguments and their applications. SIAM J. Comput.\u00a038(5), 1661\u20131694 (2008)","journal-title":"SIAM J. Comput."},{"key":"3_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1007\/978-3-540-70575-8_56","volume-title":"Automata, Languages and Programming","author":"E. Ben-Sasson","year":"2008","unstructured":"Ben-Sasson, E., Harsha, P., Lachish, O., Matsliah, A.: Sound 3-query PCPPs are long. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 686\u2013697. Springer, Heidelberg (2008)"},{"key":"3_CR39","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":"3_CR40","unstructured":"Kol, G., Raz, R.: Bounds on 2-Query Locally Testable Codes with Affine Tests. ECCC Report TR09-138 (2009)"},{"key":"3_CR41","unstructured":"Kol, G., Raz, R.: Locally testable codes analogues to the unique games conjecture do not exist. ECCC Report TR09-128 (2009)"},{"issue":"1","key":"3_CR42","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 J. Comput.\u00a035(1), 1\u201321 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"3_CR43","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1109\/TIT.1962.1057683","volume":"8","author":"R. Gallager","year":"1962","unstructured":"Gallager, R.: Low-density parity-check codes. IRE Transactions on Information Theory\u00a08(1), 21\u201328 (1962)","journal-title":"IRE Transactions on Information Theory"},{"issue":"6","key":"3_CR44","doi-asserted-by":"publisher","first-page":"1710","DOI":"10.1109\/18.556667","volume":"42","author":"M. Sipser","year":"1996","unstructured":"Sipser, M., Spielman, D.: Expander codes. IEEE Transactions on Information Theory\u00a042(6), 1710\u20131722 (1996)","journal-title":"IEEE Transactions on Information Theory"},{"key":"3_CR45","unstructured":"Spielman, D.: Computationally efficient error-correcting codes and holographic proofs. PhD thesis, MIT (1995)"},{"key":"3_CR46","unstructured":"Ben-Sasson, E., Viderman, M.: Dense locally testable codes have bad rate (2010) (unpublished manuscript)"},{"issue":"3","key":"3_CR47","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01212974","volume":"14","author":"A. Balog","year":"1994","unstructured":"Balog, A., Szemer\u00e9di, E.: A statistical theorem of set addition. Combinatorica\u00a014(3), 263\u2013268 (1994)","journal-title":"Combinatorica"},{"issue":"3","key":"3_CR48","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s000390050065","volume":"8","author":"W.T. Gowers","year":"1998","unstructured":"Gowers, W.T.: A new proof of szemer\u00e8di\u2019s theorem for arithmetic progressions of length four. Geom. Funct. Anal.\u00a08(3), 529\u2013551 (1998)","journal-title":"Geom. Funct. Anal."},{"key":"3_CR49","volume-title":"Foundations of a structural theory of set addition","author":"G.A. Freiman","year":"1973","unstructured":"Freiman, G.A.: Foundations of a structural theory of set addition, vol.\u00a037. American Mathematical Society, Providence (1973)"},{"key":"3_CR50","first-page":"323","volume":"258","author":"I.Z. Ruzsa","year":"1999","unstructured":"Ruzsa, I.Z.: An analog of freiman\u2019s theorem in groups. Ast\u00e8rique\u00a0258, 323\u2013326 (1999)","journal-title":"Ast\u00e8rique"},{"key":"3_CR51","doi-asserted-by":"crossref","unstructured":"Grigorescu, E., Kaufman, T., Sudan, M.: Succinct representation of codes with applications to testing. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 534\u2013547 (2009)","DOI":"10.1007\/978-3-642-03685-9_40"},{"key":"3_CR52","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Viderman, M.: Locally testable vs. locally decodable codes. In: Shaltiel, R. (ed.) Proc. 14th Intl. Workshop on Randomization and Computation - RANDOM 2010 (2010)","DOI":"10.1007\/978-3-642-15369-3_50"},{"key":"3_CR53","unstructured":"Woodruff, D.: New lower bounds for general locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC)\u00a014(006) (2007)"}],"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_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T18:22:06Z","timestamp":1685816526000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":53,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}