{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T00:33:23Z","timestamp":1794357203997,"version":"4.9.0"},"publisher-location":"Boston, MA","reference-count":29,"publisher":"Springer US","isbn-type":[{"value":"9780387307701","type":"print"},{"value":"9780387301624","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_202","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T14:35:05Z","timestamp":1214490905000},"page":"446-450","source":"Crossref","is-referenced-by-count":1,"title":["Linearity Testing\/Testing Hadamard Codes"],"prefix":"10.1007","author":[{"given":"Ronitt","family":"Rubinfeld","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"202_CR1_202","first-page":"188","volume-title":"Proceedings of RANDOM '03. Lecture Notes in Computer Science, vol. 2764","author":"N. Alon","year":"2003","unstructured":"Alon, N., Kaufman, T., Krivilevich, M., Litsyn, S., Ron, D.: Testing low-degree polynomials over gf(2). In: Proceedings of RANDOM '03. Lecture Notes in Computer Science, vol. 2764, pp. 188\u2013199. Springer, Berlin Heidelberg (2003)"},{"key":"202_CR2_202","first-page":"786","volume-title":"Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing","author":"S. Ar","year":"2003","unstructured":"Ar, S., Blum, M., Codenotti, B., Gemmell, P.: Checking approximate computations over the reals. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pp. 786\u2013795. ACM, New York (2003)"},{"issue":"3","key":"202_CR3_202","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. J.\u00a0ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"key":"202_CR4_202","first-page":"485","volume-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing","author":"S. Arora","year":"1997","unstructured":"Arora, S., Sudan, M.: Improved low degree testing and its applications. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pp. 485\u2013495. ACM, New York (1997)"},{"issue":"6","key":"202_CR5_202","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.: Linearity testing over characteristic two. IEEE Trans. Inf. Theory 42(6), 1781\u20131795 (1996)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"202_CR6_202","first-page":"273","volume-title":"Proceedings of APPROX-RANDOM. Lecture Notes in Computer Science, vol. 3122","author":"M. Ben-Or","year":"2004","unstructured":"Ben-Or, M., Coppersmith, D., Luby, M., Rubinfeld, R.: Non-abelian homomorphism testing, and distributions close to their self-convolutions. In: Proceedings of APPROX-RANDOM. Lecture Notes in Computer Science, vol. 3122, pp. 273\u2013285. Springer, Berlin Heidelberg (2004)"},{"key":"202_CR7_202","first-page":"612","volume-title":"Proceedings of the Thirty-Fifth Annual ACM Symposium on the Theory of Computing","author":"E. Ben-Sasson","year":"2003","unstructured":"Ben-Sasson, E., Sudan, M., Vadhan, S., Wigderson, A.: 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, pp. 612\u2013621. ACM, New York (2003)"},{"key":"202_CR8_202","first-page":"549","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. J. CSS 47, 549\u2013595 (1993)","journal-title":"J. CSS"},{"key":"202_CR9_202","unstructured":"Cleve, R., Luby, M.: A\u00a0note on self-testing\/correcting methods for trigonometric functions. In: International Computer Science Institute Technical Report TR-90-032, July 1990"},{"key":"202_CR10_202","unstructured":"Coppersmith, D.: Manuscript, private communications (1989)"},{"issue":"2","key":"202_CR11_202","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1137\/S0097539798337613","volume":"31","author":"F. Ergun","year":"2001","unstructured":"Ergun, F., Kumar, R., Rubinfeld, R.: Checking approximate computations of polynomials and functional equations. SIAM J. Comput. 31(2), 550\u2013576 (2001)","journal-title":"SIAM J. Comput."},{"key":"202_CR12_202","first-page":"32","volume-title":"Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing","author":"P. Gemmell","year":"1991","unstructured":"Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., Wigderson, A.: Self-testing\/correcting for polynomials and for approximate functions. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 32\u201342. ACM, New York (1991)"},{"issue":"4","key":"202_CR13_202","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. Hastad","year":"2001","unstructured":"Hastad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"202_CR14_202","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1002\/rsa.10068","volume":"22","author":"J. Hastad","year":"2003","unstructured":"Hastad, J., Wigderson, A.: Simple analysis of graph tests for linearity and pcp. Random Struct. Algorithms 22(2), 139\u2013160 (2003)","journal-title":"Random Struct. Algorithms"},{"key":"202_CR15_202","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1109\/FOCS.2004.64","volume-title":"Proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science","author":"C. Jutla","year":"2004","unstructured":"Jutla, C., Patthak, A., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. In: Proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science, pp. 423\u2013432. IEEE, New York (2004)"},{"key":"202_CR16_202","first-page":"317","volume-title":"Proceedings of the Forty-Sixth Annual Symposium on Foundations of Computer Science","author":"T. Kaufman","year":"2005","unstructured":"Kaufman, T., Litsyn, S.: Almost orthogonal linear codes are locally testable. In: Proceedings of the Forty-Sixth Annual Symposium on Foundations of Computer Science, pp. 317\u2013326. IEEE, New York (2005)"},{"key":"202_CR17_202","unstructured":"Kaufman, T., Litsyn, S., Xie, N.: Breaking the $$ \\epsilon $$-soundness bound of the linearity test over gf(2). Electronic Colloquium on Computational Complexity, Report TR07\u2013098, October 2007"},{"key":"202_CR18_202","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1109\/FOCS.2004.65","volume-title":"Proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science","author":"T. Kaufman","year":"2004","unstructured":"Kaufman, T., Ron, D.: Testing polynomials over general fields. In: Proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science, pp. 413\u2013422. IEEE, New York (2004)"},{"key":"202_CR19_202","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/3-540-45878-6_2","volume":"2292","author":"M. Kiwi","year":"2001","unstructured":"Kiwi, M., Magniez, F., Santha, M.: Exact and approximate testing\/correcting of algebraic functions: A\u00a0survey. Theoretical Aspects Compututer Science, LNCS 2292, 30\u201383 (2001)","journal-title":"Theoretical Aspects Compututer Science, LNCS"},{"issue":"2","key":"202_CR20_202","first-page":"371","volume":"66","author":"M. Kiwi","year":"2003","unstructured":"Kiwi, M., Magniez, F., Santha, M.: Approximate testing with error relative to input size. J. CSS 66(2), 371\u2013392 (2003)","journal-title":"J. CSS"},{"issue":"5","key":"202_CR21_202","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00224-004-1125-y","volume":"38","author":"F. Magniez","year":"2005","unstructured":"Magniez, F.: Multi-linearity self-testing with relative error. Theory Comput. Syst. 38(5), 573\u2013591 (2005)","journal-title":"Theory Comput. Syst."},{"key":"202_CR22_202","first-page":"194","volume-title":"Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing","author":"A. Polischuk","year":"1994","unstructured":"Polischuk, A., Spielman, D.: Nearly linear-size holographic proofs. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pp. 194\u2013203. ACM, New York (1994)"},{"key":"202_CR23_202","first-page":"475","volume-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing","author":"R. Raz","year":"1997","unstructured":"Raz, R., Safra, S.: A\u00a0sub-constant error-probability low-degree test, and a\u00a0sub-constant error-probability pcp characterization of np. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pp. 475\u2013484. ACM, New York (1997)"},{"issue":"6","key":"202_CR24_202","doi-asserted-by":"publisher","first-page":"1972","DOI":"10.1137\/S0097539796298625","volume":"28","author":"R. Rubinfeld","year":"1999","unstructured":"Rubinfeld, R.: On the robustness of functional equations. SIAM J. Comput. 28(6), 1972\u20131997 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"202_CR25_202","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"202_CR26_202","first-page":"191","volume-title":"Proceedings of the Thirty-Second Annual ACM Symposium on the Theory of Computing","author":"A. Samorodnitsky","year":"2000","unstructured":"Samorodnitsky, A., Trevisan, L.: A\u00a0PCP characterization of NP with optimal amortized query complexity. In: Proceedings of the Thirty-Second Annual ACM Symposium on the Theory of Computing, pp. 191\u2013199. ACM, New York (2000)"},{"key":"202_CR27_202","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1132516.1132519","volume-title":"Thirty-Eighth ACM Symposium on Theory of Computing","author":"A. Samorodnitsky","year":"2006","unstructured":"Samorodnitsky, A., Trevisan, L.: Gowers uniformity, influence of variables, and pcps. In: Thirty-Eighth ACM Symposium on Theory of Computing, pp. 11\u201320. ACM, New York (2006)"},{"key":"202_CR28_202","first-page":"427","volume-title":"Proceedings of the Thirty-Sixth Annual ACM Symposium on the Theory of Computing","author":"A. Shpilka","year":"2004","unstructured":"Shpilka, A., Wigderson, A.: Derandomizing homomorphism testing in general groups. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on the Theory of Computing, pp. 427\u2013435. ACM, NY, USA (2004)"},{"key":"202_CR29_202","first-page":"299","volume-title":"Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing","author":"L. Trevisan","year":"1998","unstructured":"Trevisan, L.: Recycling queries in pcps and in linearity tests. In: Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pp. 299\u2013308. ACM, New York (1998)"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,2]],"date-time":"2022-09-02T23:14:52Z","timestamp":1662160492000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_202"}},"subtitle":["1990; Blum, Luby, Rubinfeld"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_202","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2008]]}}}