{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:54Z","timestamp":1740109494146,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,10,29]],"date-time":"2015-10-29T00:00:00Z","timestamp":1446076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00037-015-0115-6","type":"journal-article","created":{"date-parts":[[2015,10,29]],"date-time":"2015-10-29T10:39:50Z","timestamp":1446115190000},"page":"37-77","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sparse affine-invariant linear codes are locally testable"],"prefix":"10.1007","volume":"26","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noga","family":"Ron-Zewi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,10,29]]},"reference":[{"key":"115_CR1","unstructured":"Noga Alon, Eldar Fischer, Ilan Newman,& Asaf Shapira (2006). A combinatorial characterization of the testable graph properties: it\u2019s all about regularity. In STOC, 251\u2013260. ACM. ISBN 1-59593-134-1. URL http:\/\/doi.acm.org\/10.1145\/1132516.1132555 ."},{"key":"115_CR2","doi-asserted-by":"crossref","unstructured":"Boaz Barak, Russell Impagliazzo & Avi Wigderson (2006). Extracting Randomness Using Few Independent Sources. SIAM Journal on Computing 36.","DOI":"10.1137\/S0097539705447141"},{"key":"115_CR3","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka & Madhu Sudan (2011a). On Sums of Locally Testable Affine Invariant Properties. Electronic Colloquium on Computational Complexity (ECCC) 18, 79. URL http:\/\/eccc.hpi-web.de\/report\/2011\/079 .","DOI":"10.1007\/978-3-642-22935-0_34"},{"key":"115_CR4","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka & Madhu Sudan (2011b). On Sums of Locally Testable Affine Invariant Properties. In Approximation, Randomization and yesCombinatorial Optimization. Algorithms and Techniques, volume 6845 of LNCS, 400\u2013411.","DOI":"10.1007\/978-3-642-22935-0_34"},{"issue":"7","key":"115_CR5","doi-asserted-by":"crossref","first-page":"3230","DOI":"10.1137\/090779875","volume":"39","author":"Ben-Sasson Eli","year":"2005","unstructured":"Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman (2005a) Locally Testable Codes Require Redundant Testers. SICOMP.SIAM Journal on Computing 39(7): 3230\u20133247","journal-title":"SICOMP.SIAM Journal on Computing"},{"key":"115_CR6","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Prahladh Harsha & Sofya Raskhodnikova (2005b). Some 3CNF Properties Are Hard to Test. SIAM Journal on Computing 35.","DOI":"10.1137\/S0097539704445445"},{"key":"115_CR7","unstructured":"Eli Ben-Sasson & Madhu Sudan (2010). Limits on the rate of locally testable affine-invariant codes. Electronic Colloquium on Computational Complexity (ECCC) 17, 108. URL http:\/\/eccc.hpi-web.de\/report\/2010\/108 ."},{"key":"115_CR8","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Madhu Sudan (2011). Limits on the Rate of Locally Testable Affine-Invariant Codes. In APPROX-RANDOM, volume 6845 of Lecture Notes in Computer Science, 412\u2013423. Springer. ISBN 978-3-642-22934-3. URL http:\/\/dx.doi.org\/10.1007\/978-3-642-22935-0 .","DOI":"10.1007\/978-3-642-22935-0"},{"issue":"1","key":"115_CR9","doi-asserted-by":"crossref","first-page":"75","DOI":"10.4086\/toc.2011.v007a006","volume":"7","author":"Bhattacharyya Arnab","year":"2011","unstructured":"Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie (2011) Testing Linear-Invariant Non-Linear Properties. Theory of Computing 7(1): 75\u201399","journal-title":"Theory of Computing"},{"key":"115_CR10","doi-asserted-by":"crossref","unstructured":"Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami & Shachar Lovett (2013). Every locally characterized affine-invariant property is testable. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC), 429\u2013436. ACM Press.","DOI":"10.1145\/2488608.2488662"},{"key":"115_CR11","doi-asserted-by":"crossref","unstructured":"Arnab Bhattacharyya, Elena Grigorescu & Asaf Shapira (2010). A unified framework for testing linear-invariant properties. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 478\u2013487. IEEE Computer Society.","DOI":"10.1109\/FOCS.2010.53"},{"key":"115_CR12","doi-asserted-by":"crossref","unstructured":"Christian Borgs, Jennifer T. Chayes, L\u00e1szl\u00f3 Lov\u00e1sz, Vera T. S\u00f3s, Bal\u00e1zs Szegedy & Katalin Vesztergombi (2006). Graph limits and parameter testing. In STOC, 261\u2013270. ACM. ISBN 1-59593-134-1. URL http:\/\/doi.acm.org\/10.1145\/1132516.1132556 .","DOI":"10.1145\/1132516.1132556"},{"key":"115_CR13","doi-asserted-by":"crossref","unstructured":"J. Bourgain, A.A Glibichuk & S.V. Konyagin (2006). Estimates for the Number of Sums and Products and for Exponential Sums in Fields of Prime Order. Journal of the London Mathematical Society 73(2): 380\u2013398 URL http:\/\/jlms.oxfordjournals.org\/content\/73\/2\/380.abstract .","DOI":"10.1112\/S0024610706022721"},{"key":"115_CR14","first-page":"27","volume":"14","author":"J. Bourgain","year":"2004","unstructured":"Bourgain J., Katz N., Tao T. (2004) A sum-product extimate in finite fields, and applications. GAFA 14: 27\u201357","journal-title":"GAFA"},{"key":"115_CR15","unstructured":"James Arthur Cipra (2010). Waring\u2019s number in finite fields. Ph.D. thesis, Kansas State University, Manhattan, Kansas, USA"},{"key":"115_CR16","unstructured":"Todd Cochrane & James Cipra (2011). Sum-product estimates applied to Waring\u2019s problem over finite fields. INTEGERS 11."},{"key":"115_CR17","doi-asserted-by":"crossref","unstructured":"Elena Grigorescu, Tali Kaufman & Madhu Sudan (2008). 2-Transitivity Is Insufficient for Local Testability. In IEEE Conference on Computational Complexity, 259\u2013267. IEEE Computer Society. ISBN 978-0-7695-3169-4.","DOI":"10.1109\/CCC.2008.31"},{"key":"115_CR18","doi-asserted-by":"crossref","unstructured":"Elena Grigorescu, Tali Kaufman & Madhu Sudan (2009). Succint representation of codes with applications to testing. In Proceedings of RANDOM-APPROX 2009, volume 5687 of Lecture Notes in Computer Science, 534\u2013547. Springer. URL http:\/\/dx.doi.org\/10.1007\/978-3-642-22935-0 .","DOI":"10.1007\/978-3-642-22935-0"},{"key":"115_CR19","doi-asserted-by":"crossref","unstructured":"Tali Kaufman & Simon Litsyn (2005). Almost Orthogonal Linear Codes are Locally Testable. In FOCS, 317\u2013326. IEEE Computer Society. ISBN 0-7695-2468-0.","DOI":"10.1109\/SFCS.2005.16"},{"key":"115_CR20","unstructured":"Tali Kaufman & Shachar Lovett (2010). Testing of exponentially large codes, by a new extension to Weil bound for character sums. Electronic Colloquium on Computational Complexity (ECCC) 17, 65. URL http:\/\/eccc.hpi-web.de\/report\/2010\/065 ."},{"key":"115_CR21","doi-asserted-by":"crossref","unstructured":"Tali Kaufman & Shachar Lovett (2011). New extension of the Weil bound for character sums with applications to coding. In The 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011).","DOI":"10.1109\/FOCS.2011.41"},{"key":"115_CR22","unstructured":"Tali Kaufman & Madhu Sudan (2007a). Algebraic Property Testing: The Role of Invariance. Electronic Colloquium on Computational Complexity (ECCC) 14(111). URL http:\/\/eccc.hpi-web.de\/eccc-reports\/2007\/TR07-111\/index.html ."},{"key":"115_CR23","doi-asserted-by":"crossref","unstructured":"Tali Kaufman & Madhu Sudan (2007b). Sparse Random Linear Codes are Locally Decodable and Testable. In FOCS, 590\u2013600. IEEE Computer Society.","DOI":"10.1109\/FOCS.2007.8"},{"key":"115_CR24","unstructured":"Tali Kaufman & Madhu Sudan (2008). Algebraic property testing: the role of invariance. In STOC, 403\u2013412. ACM. ISBN 978-1-60558-047-0. URL http:\/\/doi.acm.org\/10.1145\/1374376.1374434 ."},{"key":"115_CR25","doi-asserted-by":"crossref","unstructured":"Swastik Kopparty & Shubhangi Saraf (2010). Local list-decoding and testing of random linear codes from high error. In STOC, 417\u2013426. ACM Press.","DOI":"10.1145\/1806689.1806748"},{"issue":"4","key":"115_CR26","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz J.T. (1980) Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4): 701\u2013717","journal-title":"J. ACM"},{"key":"115_CR27","doi-asserted-by":"crossref","unstructured":"Asaf Shapira (2009). Greens conjecture and testing linear-invariant properties. In Proceedings of the 41st Annual ACM Symposium on the Theory of Computing (STOC), 159\u2013166. ACM Press.","DOI":"10.1145\/1536414.1536438"},{"key":"115_CR28","doi-asserted-by":"crossref","unstructured":"R. Zippel (1979). Probabilistic algorithms for sparse polynomials. In ISSAC \u201979: Proc. Int\u2019l. Symp. on Symbolic and Algebraic Computation, Lecture Notes in Computer Science, Vol. 72. Springer-Verlag.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0115-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0115-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0115-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0115-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,24]],"date-time":"2022-05-24T18:52:03Z","timestamp":1653418323000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0115-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,29]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["115"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0115-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2015,10,29]]}}}