{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:23Z","timestamp":1787337623156,"version":"build-2736575974"},"reference-count":35,"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":[[2001,1]]},"abstract":"<jats:p>A majority of the results on self-testing and correcting deal with programs which purport to compute the correct results precisely. We relax this notion of correctness and show how to check programs that compute only a numerical approximation to the correct answer. The types of programs that we deal with are those computing polynomials and functions defined by certain types of functional equations. We present results showing how to perform approximate checking, self-testing, and self-correcting of polynomials, settling in the affirmative a question raised by [P. Gemmell et al., Proceedings of the 23rd ACM Symposium on Theory of Computing, 1991, pp. 32--42; R. Rubinfeld and M. Sudan, Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, Orlando, FL, 1992, pp. 23--43; R. Rubinfeld and M. Sudan, SIAM J. Comput., 25 (1996), pp. 252--271]. We obtain this by first building approximate self-testers for linear and multilinear functions. We then show how to perform approximate checking, self-testing, and self-correcting for those functions that satisfy addition theorems, settling a question raised by [R. Rubinfeld, SIAM J. Comput., 28 (1999), pp. 1972--1997]. In both cases, we show that the properties used to test programs for these functions are both robust (in the approximate sense) and stable. Finally, we explore the use of reductions between functional equations in the context of approximate self-testing. Our results have implications for the stability theory of functional equations.<\/jats:p>","DOI":"10.1137\/s0097539798337613","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"550-576","source":"Crossref","is-referenced-by-count":5,"title":["Checking Approximate Computations of Polynomials and Functional Equations"],"prefix":"10.1137","volume":"31","author":[{"given":"Funda","family":"Erg\u00fcn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Ravi","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"J. Aczel,\n                      Lectures on Functional Equations and Their Applications\n                      , Academic Press, New York, 1966."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.4064\/ap-43-1-93-103"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"S. Ar, M. Blum, B. Codenotti, and P. Gemmell,\n                      Checking approximate computations over the reals\n                      , in Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 786\u2013795.","DOI":"10.1145\/167088.167288"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"R8","unstructured":"Manuel Blum, Michael Luby, Ronitt Rubinfeld, Self\u2010testing\/correcting with applications to numerical problems, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), Vol. 47, 1993, 549\u201359594m:65020"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/268999.269003"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/12.494097"},{"key":"R11","volume-title":"Functional equations and modelling in science and engineering","author":"Castillo Enrique","year":"1992"},{"key":"R12","first-page":"457","volume":"29","author":"Cholewa Piotr","year":"1984","journal-title":"Rev. Roumaine Math. Pures Appl."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/103147.103153"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/103147.103154"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.4064\/ap-22-2-189-198"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1080\/17442508008833155"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01831117"},{"key":"R18","first-page":"215","volume":"11","author":"Forti Gian","year":"1989","journal-title":"C. R. Math. Rep. Acad. Sci. Canada"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.4064\/ap-52-2-119-137"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson,\n                      Self\u2010testing\/correcting for polynomials and for approximate functions\n                      , in Proceedings of the 23rd ACM Symposium on Theory of Computing, 1991, pp. 32\u201342.","DOI":"10.1145\/103418.103429"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.27.4.222"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Marcos Kiwi, Fr\u00e9d\u00e9ric Magniez, Miklos Santha, Approximate testing with relative error, ACM, New York, 1999, 51\u2013602001g:65181","DOI":"10.1145\/301250.301269"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"S. Ravikumar, D. Sivakumar, On self\u2010testing without the generator bottleneck, Lecture Notes in Comput. Sci., Vol. 1026, Springer, Berlin, 1995, 248\u201326298b:68115","DOI":"10.1007\/3-540-60692-0_53"},{"key":"R24","unstructured":"Richard Lipton, New directions in testing, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 2, Amer. Math. Soc., Providence, RI, 1991, 191\u201320292c:68127"},{"key":"R25","unstructured":"G. G. Lorentz,\n                      Approximation of Functions\n                      , Holt, Rinehart and Winston, New York, 1966."},{"key":"R26","volume-title":"The power of interaction","author":"Lund Carsten","year":"1992"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.4064\/sm-5-1-50-68"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298625"},{"key":"R29","unstructured":"Ronitt Rubinfeld, Madhu Sudan, Self\u2010testing polynomial functions efficiently and over rational domains, ACM, New York, 1992, 23\u20133293f:68067"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R31","first-page":"377","volume":"117","author":"Skof Fulvia","year":"1983","journal-title":"Atti Accad. Sci. Torino Cl. Sci. Fis. Mat. Natur."},{"key":"R32","unstructured":"M. Sudan,\n                      private communication\n                      , University of California, Berkeley, 1991."},{"key":"R33","volume-title":"Theory of approximation of functions of a real variable","author":"Timan A.","year":"1963"},{"key":"R34","unstructured":"E. C. Titchmarsh,\n                      The Theory of Functions\n                      , Oxford University Press, 1947."},{"key":"R35","unstructured":"F. Vainstein,\n                      Algebraic Methods in Hardware\/Software Testing\n                      , Ph.D. Thesis, Boston University, Boston, MA, 1993."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539798337613","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:21:34Z","timestamp":1787336494000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539798337613"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539798337613"],"URL":"https:\/\/doi.org\/10.1137\/s0097539798337613","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}