{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:21:58Z","timestamp":1772083318553,"version":"3.50.1"},"publisher-location":"New York, NY","reference-count":26,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_202","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:20Z","timestamp":1461269000000},"page":"1107-1110","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Linearity Testing\/Testing Hadamard Codes"],"prefix":"10.1007","author":[{"given":"Sofya","family":"Raskhodnikova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"691_CR12205","doi-asserted-by":"crossref","unstructured":"Alon N, Kaufman T, Krivilevich M, Litsyn S, Ron D (2003) Testing low-degree polynomials over GF(2). In: Proceedings of RANDOM\u201903, Princeton, pp 188\u2013199","DOI":"10.1007\/978-3-540-45198-3_17"},{"key":"691_CR12206","first-page":"786","volume-title":"Checking approximate computations over the reals","author":"S Ar","year":"1993","unstructured":"Ar S, Blum M, Codenotti B, Gemmell P (1993) Checking approximate computations over the reals. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, San Diego, pp\u00a0786\u2013795"},{"issue":"3","key":"691_CR12207","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 (1998) Proof verification and the hardness of approximation problems. J ACM 45(3): 501\u2013555","journal-title":"J ACM"},{"issue":"4","key":"691_CR12208","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1006\/jcss.2001.1747","volume":"62","author":"Y Aumann","year":"2001","unstructured":"Aumann Y, H\u00e5stad J, Rabin MO, Sudan M (2001) Linear-consistency testing. J Comput Syst Sci 62(4):589\u2013607","journal-title":"J Comput Syst Sci"},{"issue":"6","key":"691_CR12209","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1109\/18.556674","volume":"42","author":"M Bellare","year":"1996","unstructured":"Bellare M, Coppersmith D, H\u00e5stad J, Kiwi M, Sudan M (1996) Linearity testing over characteristic two. IEEE Trans Inf Theory 42(6):1781\u20131795","journal-title":"IEEE Trans Inf Theory"},{"issue":"3","key":"691_CR12210","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 (1998) Free bits, PCPs, and nonapproximability\u2014towards tight results. SIAM J Comput 27(3):804\u2013915","journal-title":"SIAM J Comput"},{"issue":"1","key":"691_CR12211","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1002\/rsa.20182","volume":"32","author":"M Ben-Or","year":"2008","unstructured":"Ben-Or M, Coppersmith D, Luby M, Rubinfeld R (2008) Non-Abelian homomorphism testing, and distributions close to their self-convolutions. Random Struct Algorithms 32(1):49\u201370","journal-title":"Random Struct Algorithms"},{"key":"691_CR12212","first-page":"612","volume-title":"Randomness-efficient low degree tests and short PCPs via epsilon-biased sets","author":"E Ben-Sasson","year":"2003","unstructured":"Ben-Sasson E, Sudan M, Vadhan S, Wigderson A (2003) Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on the Theory of Computing, San Diego, pp\u00a0612\u2013621"},{"key":"691_CR12213","first-page":"549","volume":"47","author":"M Blum","year":"1993","unstructured":"Blum M, Luby M, Rubinfeld R (1993) Self-testing\/correcting with applications to numerical problems. JCSS 47:549\u2013595","journal-title":"JCSS"},{"key":"691_CR12214","doi-asserted-by":"crossref","unstructured":"Ergun F, Kumar R, Rubinfeld R (2001) Checking approximate computations of polynomials and functional equations. SIAM J Comput 31(2):s 550\u2013576","DOI":"10.1137\/S0097539798337613"},{"key":"691_CR12215","first-page":"32","volume-title":"Self-testing\/correcting for polynomials and for approximate functions","author":"P Gemmell","year":"1991","unstructured":"Gemmell P, Lipton R, Rubinfeld R, Sudan M, Wigderson A (1991) Self-testing\/correcting for polynomials and for approximate functions. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, New Orleans, pp\u00a032\u201342"},{"issue":"4","key":"691_CR12216","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 (1998) Property testing and its connection to learning and approximation. J ACM 45(4):653\u2013750","journal-title":"J ACM"},{"issue":"4","key":"691_CR12217","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad J (2001) Some optimal in approximability results. J ACM 48(4):798\u2013859","journal-title":"J ACM"},{"issue":"2","key":"691_CR12218","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1002\/rsa.10068","volume":"22","author":"J Hastad","year":"2003","unstructured":"Hastad J, Wigderson A (2003) Simple analysis of graph tests for linearity and PCP. Random Struct Algorithms 22(2):139\u2013160","journal-title":"Random Struct Algorithms"},{"issue":"2","key":"691_CR12219","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1002\/rsa.20262","volume":"35","author":"CS Jutla","year":"2009","unstructured":"Jutla CS, Patthak AC, Rudra A, Zuckerman D (2009) Testing low-degree polynomials over prime fields. Random Struct Algorithms 35(2): 163\u2013193","journal-title":"Random Struct Algorithms"},{"issue":"3","key":"691_CR12220","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1137\/S0097539704445615","volume":"36","author":"T Kaufman","year":"2006","unstructured":"Kaufman T, Ron D (2006) Testing polynomials over general fields. SIAM J Comput 36(3):779\u2013802","journal-title":"SIAM J Comput"},{"issue":"5","key":"691_CR12221","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1137\/080715548","volume":"39","author":"T Kaufman","year":"2010","unstructured":"Kaufman T, Litsyn S, Xie N (2010) Breaking the epsilon-soundness bound of the linearity test over GF(2). SIAM J Comput 39(5):1988\u20132003","journal-title":"SIAM J Comput"},{"key":"691_CR12222","unstructured":"Kiwi M, Magniez F, Santha M (2001) Exact and approximate testing\/correcting of algebraic functions: a survey. Electron. Colloq. Comput. Complex. 8(14). \n                  http:\/\/dblp.uni-trier.de\/db\/journals\/eccc\/eccc8.html#ECCC-TR01-014"},{"issue":"2","key":"691_CR12223","first-page":"371","volume":"66","author":"M Kiwi","year":"2003","unstructured":"Kiwi M, Magniez F, Santha M (2003) Approximate testing with error relative to input size. JCSS 66(2):371\u2013392","journal-title":"JCSS"},{"issue":"5","key":"691_CR12224","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00224-004-1125-y","volume":"38","author":"F Magniez","year":"2005","unstructured":"Magniez F (2005) Multi-linearity self-testing with relative error. Theory Comput Syst 38(5):573\u2013591","journal-title":"Theory Comput Syst"},{"key":"691_CR12225","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell R (2014) Analysis of Boolean Functions. Cambridge University Press, New York"},{"issue":"1","key":"691_CR12226","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"M Parnas","year":"2002","unstructured":"Parnas M, Ron D, Samorodnitsky A (2002) Testing basic Boolean formulae. SIAM J Discret Math 16(1):20\u201346","journal-title":"SIAM J Discret Math"},{"issue":"2","key":"691_CR12227","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R Rubinfeld","year":"1996","unstructured":"Rubinfeld R, Sudan M (1996) Robust characterizations of polynomials with applications to program testing. SIAM J Comput 25(2):252\u2013271","journal-title":"SIAM J Comput"},{"key":"691_CR12228","first-page":"191","volume-title":"A PCP characterization of NP with optimal amortized query complexity","author":"A Samorodnitsky","year":"2000","unstructured":"Samorodnitsky A, Trevisan L (2000) A PCP characterization of NP with optimal amortized query complexity. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, Portland, pp\u00a0191\u2013199"},{"issue":"4","key":"691_CR12229","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1137\/S009753970444658X","volume":"36","author":"A Shpilka","year":"2006","unstructured":"Shpilka A, Wigderson A (2006) Derandomizing homomorphism testing in general groups. SIAM J Comput 36(4):1215\u20131230","journal-title":"SIAM J Comput"},{"key":"691_CR12230","first-page":"299","volume-title":"Recycling queries in PCPs and in linearity tests","author":"L Trevisan","year":"1998","unstructured":"Trevisan L (1998) Recycling queries in PCPs and in linearity tests. In: Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, pp\u00a0299\u2013308"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:25:05Z","timestamp":1553095505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_202","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}