{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:25:19Z","timestamp":1725600319173},"publisher-location":"Berlin, Heidelberg","reference-count":23,"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_34","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T09:20:39Z","timestamp":1313140839000},"page":"400-411","source":"Crossref","is-referenced-by-count":12,"title":["On Sums of Locally Testable Affine Invariant Properties"],"prefix":"10.1007","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Grigorescu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ghid","family":"Maatouk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"34_CR1","first-page":"251","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing","author":"N. Alon","year":"2006","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: it\u2019s all about regularity. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, pp. 251\u2013260. ACM, New York (2006)"},{"issue":"11","key":"34_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":"34_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":"34_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":"#cr-split#-34_CR5.1","doi-asserted-by":"crossref","unstructured":"Barak, B., Dvir, Z., Wigderson, A., Yehudayoff, A.: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In: Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a017, p. 149 (2010);","DOI":"10.1145\/1993636.1993705"},{"key":"#cr-split#-34_CR5.2","unstructured":"To appear in STOC 2011"},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1007\/s00453-008-9272-1","volume":"58","author":"O. Barkol","year":"2010","unstructured":"Barkol, O., Ishai, Y., Weinreb, E.: On locally decodable codes, self-correctable codes, and t-private PIR. Algorithmica\u00a058, 831\u2013859 (2010)","journal-title":"Algorithmica"},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Grigorescu, E., Maatouk, G., Shpilka, A., Sudan, M.: On sums of locally testable affine invariant properties. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 18, p. 79 (2011)","DOI":"10.1007\/978-3-642-22935-0_34"},{"key":"#cr-split#-34_CR8.1","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Maatouk, G., Shpilka, A., Sudan, M.: Symmetric LDPC codes are not necessarily locally testable. In: Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a017, p. 199 (2010);","DOI":"10.1109\/CCC.2011.14"},{"key":"#cr-split#-34_CR8.2","unstructured":"To appear in CCC 2011"},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M.: Limits on the rate of locally testable affine-invariant codes. In: Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a017, p. 108 (2010)","DOI":"10.1007\/978-3-642-22935-0_35"},{"key":"34_CR10","first-page":"261","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing","author":"C. Borgs","year":"2006","unstructured":"Borgs, C., Chayes, J.T., Lov\u00e1sz, L., S\u00f3s, V.T., Szegedy, B., Vesztergombi, K.: Graph limits and parameter testing. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, pp. 261\u2013270. ACM, New York (2006)"},{"issue":"6","key":"34_CR11","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\u2013981 (1998)","journal-title":"Journal of the ACM"},{"issue":"4","key":"34_CR12","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)","journal-title":"Journal of the ACM"},{"key":"34_CR13","first-page":"259","volume-title":"Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008","author":"E. Grigorescu","year":"2008","unstructured":"Grigorescu, E., Kaufman, T., Sudan, M.: 2-transitivity is insufficient for local testability. In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, College Park, Maryland, USA, June 23-26, pp. 259\u2013267. IEEE Computer Society, Los Alamitos (2008)"},{"key":"34_CR14","doi-asserted-by":"crossref","unstructured":"Grigorescu, E., Kaufman, T., Sudan, M.: Succinct Representation of Codes with Applications to Testing. In: Dinur, I., Jansen, K., Naor, J., Rolim, J.D.P. (eds.) APPROX-RANDOM 2009. LNCS, vol.\u00a05687, pp. 534\u2013547. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-03685-9_40"},{"issue":"2","key":"34_CR15","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1002\/rsa.20262","volume":"35","author":"C.S. Jutla","year":"2009","unstructured":"Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. Random Struct. Algorithms\u00a035(2), 163\u2013193 (2009)","journal-title":"Random Struct. Algorithms"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC 2000, pp. 80\u201386. ACM, New York (2000)","DOI":"10.1145\/335305.335315"},{"issue":"3","key":"34_CR17","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. on Computing\u00a036(3), 779\u2013802 (2006)","journal-title":"SIAM J. on Computing"},{"key":"34_CR18","unstructured":"Kaufman, T., Lovett, S.: Testing of exponentially large codes, by a new extension to Weil bound for character sums. In: Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a017, p. 65 (2010)"},{"key":"34_CR19","first-page":"403","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"T. Kaufman","year":"2008","unstructured":"Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: Dwork, C. (ed.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, pp. 403\u2013412. ACM, New York (2008)"},{"issue":"2","key":"34_CR20","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. on Computing\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM J. on Computing"},{"key":"34_CR21","doi-asserted-by":"crossref","unstructured":"Sudan, M.: Invariance in property testing. In: Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a017, p. 51 (2010)","DOI":"10.1007\/978-3-642-16367-8_12"}],"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_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T08:27:12Z","timestamp":1638260832000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}