{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T15:40:10Z","timestamp":1741448410464,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_35","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T09:20:39Z","timestamp":1313140839000},"page":"412-423","source":"Crossref","is-referenced-by-count":8,"title":["Limits on the Rate of Locally Testable Affine-Invariant Codes"],"prefix":"10.1007","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: it\u2019s all about regularity. In: STOC 2006, pp. 251\u2013260 (2006)","DOI":"10.1145\/1132516.1132555"},{"issue":"11","key":"35_CR2","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":"35_CR3","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":"1","key":"35_CR4","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"},{"key":"35_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC 1991, pp. 21\u201332 (1991)","DOI":"10.1145\/103418.103428"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Guruswami, V., Kaufman, T., Sudan, M., Viderman, M.: Locally testable codes require redundant testers. In: CCC 2009, pp. 52\u201361 (2009)","DOI":"10.1109\/CCC.2009.6"},{"key":"35_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF properties are hard to test. SIAM J. Comput.\u00a035(1), 1\u201321 (2005)","DOI":"10.1137\/S0097539704445445"},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Maatouk, G., Shpilka, A., Sudan, M.: Symmetric LDPC codes are not necessarily locally testable. In: CCC (2011)","DOI":"10.1109\/CCC.2011.14"},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M.: Simple PCPs with poly-log rate and query complexity. In: STOC 2005, pp. 266\u2013275 (2005)","DOI":"10.1145\/1060590.1060631"},{"key":"35_CR10","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Kopparty, S., Schoenebeck, G., Sudan, M., Zuckerman, D.: Optimal testing of Reed-Muller codes. In: FOCS 2010, pp. 488\u2013497 (2010)","DOI":"10.1109\/FOCS.2010.54"},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. In: STOC 1982, pp. 73\u201383 (1982)","DOI":"10.1145\/100216.100225"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J.T., Lov\u00e1sz, L., S\u00f3s, V.T., Szegedy, B., Vesztergombi, K.: Graph limits and parameter testing. In: STOC 2006, pp. 261\u2013270 (2006)","DOI":"10.1145\/1132516.1132556"},{"key":"35_CR13","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, 965\u2013981 (1998)","journal-title":"Journal of the ACM"},{"issue":"3","key":"35_CR14","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"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. In: STOC 2009, pp. 39\u201344 (2009)","DOI":"10.1145\/1536414.1536422"},{"issue":"4","key":"35_CR16","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"},{"issue":"4","key":"35_CR17","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. J. ACM\u00a053(4), 558\u2013655 (2006)","journal-title":"J. ACM"},{"key":"35_CR18","doi-asserted-by":"crossref","unstructured":"Grigorescu, E., Kaufman, T., Sudan, M.: 2-transitivity is insufficient for local testability. In: CCC 2008, pp. 259\u2013267 (2008)","DOI":"10.1109\/CCC.2008.31"},{"key":"35_CR19","doi-asserted-by":"crossref","unstructured":"Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. In: FOCS 2004, pp. 423\u2013432 (2004)","DOI":"10.1109\/FOCS.2004.64"},{"issue":"5-6","key":"35_CR20","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1016\/S0019-9958(67)90691-2","volume":"11","author":"T. Kasami","year":"1967","unstructured":"Kasami, T., Lin, S., Peterson, W.: Some results on cyclic codes which are invariant under the affine group and their applications. Information and Control\u00a011(5-6), 475\u2013496 (1967)","journal-title":"Information and Control"},{"key":"35_CR21","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: STOC 2000, pp. 80\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"key":"35_CR22","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Ron, D.: Testing polynomials over general fields. In: FOCS 2004, pp. 413\u2013422 (2004)","DOI":"10.1109\/FOCS.2004.65"},{"key":"35_CR23","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: STOC 2008, pp. 403\u2013412 (2008)","DOI":"10.1145\/1374376.1374434"},{"key":"35_CR24","doi-asserted-by":"crossref","unstructured":"Polishchuk, A., Spielman, D.A.: Nearly-linear size holographic proofs. In: STOC 1994, pp. 194\u2013203 (1994)","DOI":"10.1145\/195058.195132"},{"issue":"2","key":"35_CR25","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 J. Comput.\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"35_CR26","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A.: Low-degree tests at large distances. In: STOC 2007, pp. 506\u2013515 (2007)","DOI":"10.1145\/1250790.1250864"},{"key":"35_CR27","unstructured":"Sudan, M.: Efficient checking of polynomials and proofs and the hardness of approximation problems. PhD thesis, UC Berkeley (1992)"},{"key":"35_CR28","unstructured":"Woodruff, D.: New lower bounds for general locally decodable codes. In: Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a0(006) (2007)"},{"key":"35_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1326554.1326555","volume":"55","author":"S. Yekhanin","year":"2008","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. Journal of the ACM\u00a055, 1\u201316 (2008)","journal-title":"Journal of the ACM"},{"key":"35_CR30","doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Locally decodable codes. In: Foundations and Trends in Theoretical Computer Science (2011)","DOI":"10.1007\/978-3-642-20712-9_22"}],"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-22935-0_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T15:18:28Z","timestamp":1741447108000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}