{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:16:41Z","timestamp":1792156601840,"version":"4.4.0"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1996,4]]},"abstract":"<jats:p>The study of self-testing and self-correcting programs leads to the search for robust characterizations of functions. Here the authors make this notion precise and show such a characterization for polynomials. From this characterization, the authors get the following applications. Simple and efficient self-testers for polynomial functions are constructed. The characterizations provide results in the area of coding theory by giving extremely fast and efficient error-detecting schemes for some well-known codes. This error-detection scheme plays a crucial role in subsequent results on the hardness of approximating some NP-optimization problems.<\/jats:p>","DOI":"10.1137\/s0097539793255151","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:43:31Z","timestamp":1109227411000},"page":"252-271","source":"Crossref","is-referenced-by-count":570,"title":["Robust Characterizations of Polynomials with Applications to Program Testing"],"prefix":"10.1137","volume":"25","author":[{"given":"Ronitt","family":"Rubinfeld","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RAHK","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1125"},{"key":"RALMSS92","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy,  Proof verification and the intractability of approximation problems,  Proc. 33rd IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ,  1992,  14\u201323 0977.68539","DOI":"10.1109\/SFCS.1992.267823"},{"key":"RAS92","doi-asserted-by":"crossref","unstructured":"S. Arora, S. Safra,  Probabilistic checking of proofs: A new characterization of NP,  Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ,  1992,  2\u201313 0945.68516","DOI":"10.1109\/SFCS.1992.267824"},{"key":"RBAB93","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56503-5_52"},{"key":"RBF90","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52282-4_30"},{"key":"RBF91","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200057"},{"key":"RBFL91","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"RBFLS91","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin, M. Szegedy,  Checking computations in polylogarithmic time,  Proc. 23rd Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1991,  21\u201331","DOI":"10.1145\/103418.103428"},{"key":"RBGLR93","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, A. Russell,  Efficient probabilistically checkable proofs,  Proc. 25th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1993,  294\u2013304","DOI":"10.1145\/167088.167174"},{"key":"RBK89","doi-asserted-by":"crossref","unstructured":"M. Blum, S. Kannan,  Program correctness checking . and the design of programs that check their work,  Proc. 21st Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1989,  86\u201397","DOI":"10.1145\/73007.73015"},{"key":"RBLR90","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"RBLU88","unstructured":"M. Blum,  Designing programs to check their work, Tech. report, TR\u201388\u2013009, International Computer Science Institute, Berkeley, CA,  1988"},{"key":"RDW70","volume-title":"Algebra. Vol 1","author":"Van der Waerden B.","year":"1970"},{"key":"RFGLSS91","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lovasz, S. Safra, M. Szegedy,  Approximating clique is almost NP-complete,  Proc. 32nd IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ,  1991,  2\u201312","DOI":"10.1109\/SFCS.1991.185341"},{"key":"RFHS94","unstructured":"Katalin Friedl, Zsolt Hatsagi, Alexander Shen,  Low-degree tests,  Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994), ACM, New York,  1994,  57\u201364 95d:680550869.65084"},{"key":"RFL92A","doi-asserted-by":"crossref","unstructured":"U. Feige, L. Lovasz,  Two-prover one-round proof systems: Their power and their problems,  Proc. 24th ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1992,  733\u2013744","DOI":"10.1145\/129712.129783"},{"key":"RFS94","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1995.377032"},{"key":"RGLRSW91","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, A. Wigderson,  Self-testing\/correcting for polynomials and for approximate functions,  Proc. 23rd Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1991,  32\u201342","DOI":"10.1145\/103418.103429"},{"key":"RKAN90","unstructured":"S. Kannan, Ph.D. Thesis,  Program result checking with applications, University of California at Berkeley, Berkeley, CA,  1990"},{"key":"RLIP91","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/002\/13"},{"key":"RLS91","doi-asserted-by":"crossref","unstructured":"D. Lapidot, A. Shamir,  Fully parallelized multi prover protocols for NEXP-TIME,  Proc. 32nd IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ,  1991,  13\u201318","DOI":"10.1109\/SFCS.1991.185342"},{"key":"RLUN92","volume-title":"The power of interaction","author":"Lund Carsten","year":"1992"},{"key":"RNAO92","unstructured":"M. Naor,  1992, personal communication, April"},{"key":"RPS94","doi-asserted-by":"crossref","unstructured":"A. Polishchuk, D. Spielman,  Nearly-linear size holographic proofs,  Proc. 26th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1994,  194\u2013203","DOI":"10.1145\/195058.195132"},{"key":"RRS92","unstructured":"Ronitt Rubinfeld, Madhu Sudan,  Self-testing polynomial functions efficiently and over rational domains,  Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, FL, 1992), ACM, New York,  1992,  23\u201332 93f:680670834.68076"},{"key":"RRUB90","unstructured":"R. Rubinfeld, Ph.D. Thesis,  A mathematical theory of self-checking, self testing and self-correcting programs, University of California at Berkeley, Berkeley, CA,  1990"},{"key":"RSHE91","unstructured":"A. Shen,  1991, personal communication, May"},{"key":"RSUD92","unstructured":"M. Sudan, Ph.D. Thesis,  Efficient checking of polynomials and proofs and the hardness of approximation problems, University of California at Berkeley, Berkeley, CA,  1992"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793255151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:56:06Z","timestamp":1787338566000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793255151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1996,4]]}},"alternative-id":["10.1137\/S0097539793255151"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793255151","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,4]]}}}