{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:00Z","timestamp":1787337480956,"version":"build-2736575974"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>In this paper, we study the general question of how characteristics of functional equations influence whether or not they are robust. We isolate examples of properties which are necessary for the functional equations to be robust. On the other hand, we show other properties which are sufficient for robustness. We then study a general class of functional equations, which are of the form $\\forall x,y F[f(x-y), f(x+y), f(x),f(y)]=0, where F is an algebraic function. We give conditions on such functional equations that imply robustness.<\/jats:p>\n                  <jats:p>Our results have applications to the area of self-testing\/correcting programs. We show that self-testers and self-correctors can be found for many functions satisfying robust functional equations, including algebraic functions of trigonometric functions such as $\\tan{x},{1 \\over {1+\\cot{x}}},$ ${Ax \\over {1-Ax}},cosh x.<\/jats:p>","DOI":"10.1137\/s0097539796298625","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1972-1997","source":"Crossref","is-referenced-by-count":33,"title":["On the Robustness of Functional Equations"],"prefix":"10.1137","volume":"28","author":[{"given":"Ronitt","family":"Rubinfeld","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90018-4"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1125"},{"key":"R3","unstructured":"J. Acz\u00e9l,\n                      Lectures on Functional Equations and Applications\n                      , Academic Press, New York, 1966."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1790-9"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"S. Ar, M. Blum, B. Codenotti, and P. Gemmell,\n                      Checking approximate computations over the reals\n                      , in Proc. 25th Annual ACM Symp. Theory of Computing, 1993, pp. 786\u2013795.","DOI":"10.1145\/167088.167288"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy,\n                      Proof verification and the intractability of approximation problems\n                      , in Proc. 33rd IEEE Symp. Foundations of Computer Science, 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra,\n                      Probabilistic checking of proofs: A new characterization of NP\n                      , in Proc. 33rd Annual IEEE Symp. Foundations of Computer Science, 1992, pp. 2\u201313.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Donald Beaver, Joan Feigenbaum, Hiding instances in multioracle queries (extended abstract), Lecture Notes in Comput. Sci., Vol. 415, Springer, Berlin, 1990, 37\u2013481063302","DOI":"10.1007\/3-540-52282-4_30"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin, and M. Szegedy,\n                      Checking computations in polylogarithmic time\n                      , in Proc. 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 21\u201331.","DOI":"10.1145\/103418.103428"},{"key":"R11","unstructured":"M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi, and M. Sudan,\n                      Linearity testing in characteristic two\n                      , Proc. 36th Annual Symp. Foundations of Computer Science, 1995, pp. 434\u2013441."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, and A. Russell,\n                      Efficient probabilistically checkable proofs\n                      , in Proc. 25th Annual ACM Symp. Theory of Computing, 1993, pp. 294\u2013304.","DOI":"10.1145\/167088.167174"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan,\n                      Improved non\u2010approximability results\n                      , in Proc. ACM Symp. Theory of Computing, 1994, pp. 184\u2013193.","DOI":"10.1145\/195058.195129"},{"key":"R15","unstructured":"M. Blum,\n                      Designing Programs to Check Their Work\n                      , Tech. report TR\u201088\u2010009, International Computer Science Institute, University of California at Berkeley, Berkeley, CA, 1988."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"M. Blum, B. Codenotti, P. Gemmell, and T. Shahoumian, Self\u2010Correcting for Function Fields of Finite Transcendental Degree, Procc. 22nd Internat. Colloquium ICALP 95, Lecture Notes in Comput. Sci. 944, 1995, pp. 547\u2013557.","DOI":"10.1007\/3-540-60084-1_104"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor,\n                      Checking the correctness of memories\n                      , Proc. 32nd Annual Symp. Foundations of Computer Science, 1991, pp. 90\u201399.","DOI":"10.1109\/SFCS.1991.185352"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M. Blum and S. Kannan,\n                      Program correctness checking. and the design of programs that check their work\n                      , in Proc. 21st Annual ACM Symp. on Theory of Computing, 1989, pp. 86\u201397.","DOI":"10.1145\/73007.73015"},{"key":"R19","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":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Manuel Blum, Hal Wasserman, Program result\u2010checking: a theory of testing meets a test of theory, IEEE Comput. Soc. Press, Los Alamitos, CA, 1994, 382\u20133921489245","DOI":"10.1109\/SFCS.1994.365678"},{"key":"R22","volume-title":"Functional equations and modelling in science and engineering","author":"Castillo Enrique","year":"1992"},{"key":"R23","unstructured":"R. Cleve and M. Luby,\n                      A Note on Self\u2010Testing\/Correcting Methods for Trigonometric Functions\n                      , Tech. report TR\u201090\u2010032, International Computer Science Institute, University of California at Berkeley, Berkeley, CA, 1990."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/103147.103153"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/103147.103154"},{"key":"R26","unstructured":"D. Coppersmith, untitled manuscript, December 1989 (result described in [19])."},{"key":"R27","unstructured":"F. Erg\u00fcn, S. R. Kumar, and R. Rubinfeld,\n                      Approximate checking of polynomials and functional equations\n                      , Proc. 37th IEEE Symp. Foundations of Computer Science, 1996, pp. 292\u2013303."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796311168"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy,\n                      Approximating clique is almost NP\u2010complete\n                      , in Proc. 32nd IEEE Symp. on Foundations of Computer Science, 1991, pp. 2\u201312.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0222061"},{"key":"R31","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 Proc. 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 32\u201342.","DOI":"10.1145\/103418.103429"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/0213011"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"S. Kumar, D. Sivakumar, Efficient self\u2010testing\/self\u2010correction of linear recurrences, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 602\u20136111450658","DOI":"10.1109\/SFCS.1996.548519"},{"key":"R34","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":"R35","doi-asserted-by":"crossref","unstructured":"S. Micali,\n                      Computationally\u2010sound proofs\n                      , Proc. 35th Annual Symp. Foundations of Computer Science, 1994, pp. 436\u2013453.","DOI":"10.1109\/SFCS.1994.365746"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"A. Polischuk and D. Spielman,\n                      Nearly linear size holographic proofs\n                      , Proc. 26th ACM Symp. on Theory of Computing, 1994, pp. 194\u2013203.","DOI":"10.1145\/195058.195132"},{"key":"R37","unstructured":"Ronitt Rubinfeld, Madhu Sudan, Self\u2010testing polynomial functions efficiently and over rational domains, ACM, New York, 1992, 23\u20133293f:68067"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R39","unstructured":"N. Schriver, personal communication, February 1990."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60615-7"},{"key":"R41","unstructured":"M. Sudan, personal communication, 1994."},{"key":"R42","doi-asserted-by":"crossref","unstructured":"F. Vainstein, Error detection and correction in numerical computations by algebraic methods, Lecture Notes in Comput. Sci., Vol. 539, Springer, Berlin, 1991, 456\u201346494d:68050","DOI":"10.1007\/3-540-54522-0_133"},{"key":"R43","unstructured":"F. Vainstein,\n                      Algebraic Methods in Hardware\/Software Testing\n                      , Ph.D. thesis, Boston University, Boston, MA, 1993."},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1007\/BF01293262"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1155\/1998\/28524"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00207-4"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"R. Zippel,\n                      Effective Polynomial Computation\n                      , Kluwer Academic Publishers, Norwell, MA, 1993.","DOI":"10.1007\/978-1-4615-3188-3"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539796298625","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:28Z","timestamp":1787335948000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539796298625"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":47,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1137\/S0097539796298625"],"URL":"https:\/\/doi.org\/10.1137\/s0097539796298625","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}