{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:00:51Z","timestamp":1778292051608,"version":"3.51.4"},"reference-count":27,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3827,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,3]]},"DOI":"10.1016\/s0022-0000(03)00004-7","type":"journal-article","created":{"date-parts":[[2003,4,30]],"date-time":"2003-04-30T23:27:29Z","timestamp":1051745249000},"page":"371-392","source":"Crossref","is-referenced-by-count":4,"title":["Approximate testing with error relative to input size"],"prefix":"10.1016","volume":"66","author":[{"given":"Marcos","family":"Kiwi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Magniez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(03)00004-7_BIB1","doi-asserted-by":"crossref","first-page":"93","DOI":"10.4064\/ap-43-1-93-103","article-title":"Functions with bounded nth difference","volume":"43","author":"Albert","year":"1983","journal-title":"Ann. Polonici Math."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB2","doi-asserted-by":"crossref","unstructured":"S. Ar, M. Blum, B. Codenotti, P. Gemmell, Checking approximate computations over the reals, in: Proceedings of the 25th STOC, 1993, pp. 786\u2013795.","DOI":"10.1145\/167088.167288"},{"key":"10.1016\/S0022-0000(03)00004-7_BIB3","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and intractability of approximation problems, in: Proceedings of the 33rd FOCS, 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"10.1016\/S0022-0000(03)00004-7_BIB4","doi-asserted-by":"crossref","unstructured":"D. Beaver, J. Feigenbaum, Hiding instances in multioracle queries, in: Proceedings of the Seventh STACS, Lecture Notes in Computer Science, Vol. 415, 1990, pp. 37\u201348.","DOI":"10.1007\/3-540-52282-4_30"},{"key":"10.1016\/S0022-0000(03)00004-7_BIB5","unstructured":"M. Blum, Designing programs to check their work, Technical Report TR-88-009, ICSI, 1988."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB6","doi-asserted-by":"crossref","unstructured":"M. Blum, S. Kannan, Designing programs that check their work, in: Proceedings of the 21st STOC, 1989, pp. 86\u201397.","DOI":"10.1145\/73007.73015"},{"key":"10.1016\/S0022-0000(03)00004-7_BIB7","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","article-title":"Self-testing\/correcting with applications to numerical problems","volume":"47","author":"Blum","year":"1993","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB8","doi-asserted-by":"crossref","unstructured":"M. Blum, H. Wasserman, Program result-checking: a theory of testing meets a test of theory, in: Proceedings of the 35th FOCS, 1994, pp. 382\u2013392.","DOI":"10.1109\/SFCS.1994.365678"},{"key":"10.1016\/S0022-0000(03)00004-7_BIB9","unstructured":"D. Coppersmith, Manuscript, See discussion in [6], December 1989."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB10","doi-asserted-by":"crossref","first-page":"189","DOI":"10.4064\/ap-22-2-189-198","article-title":"A representation theorem for (X1\u22121)(X2\u22121)\u2026 (Xn\u22121) and its applications","volume":"22","author":"Djokovi\u0107","year":"1969","journal-title":"Ann. Polonici Math."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB11","doi-asserted-by":"crossref","unstructured":"F. Erg\u00fcn, S. Ravi Kumar, R. Rubinfeld, Approximate checking of polynomials and functional equations, in: Proceedings of the 37th FOCS, 1996, pp. 592\u2013601.","DOI":"10.1109\/SFCS.1996.548518"},{"key":"10.1016\/S0022-0000(03)00004-7_BIB12","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF01831117","article-title":"Hyers\u2013Ulam stability of functional equations in several variables","volume":"50","author":"Forti","year":"1995","journal-title":"Aeq. Math."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB13","doi-asserted-by":"crossref","first-page":"119","DOI":"10.4064\/ap-52-2-119-137","article-title":"Local stability of the functional equation characterizing polynomial functions","volume":"42","author":"Gajda","year":"1990","journal-title":"Ann. Polonici Math."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB14","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Goldwasser, D. Ron, Property testing and its connection to learning and approximation, in: Proceedings of the 37th FOCS, 1996, pp. 339\u2013348.","DOI":"10.1109\/SFCS.1996.548493"},{"key":"10.1016\/S0022-0000(03)00004-7_BIB15","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, A. Wigderson, Self-testing\/correcting for polynomials and for approximate functions, in: Proceedings of the 23rd STOC, 1991, pp. 32\u201342.","DOI":"10.1145\/103418.103429"},{"key":"10.1016\/S0022-0000(03)00004-7_BIB16","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1073\/pnas.27.4.222","article-title":"On the stability of the linear functional equation","volume":"27","author":"Hyers","year":"1941","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"10.1016\/S0022-0000(03)00004-7_BIB17","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF01830975","article-title":"Approximate homomorphisms","volume":"44","author":"Hyers","year":"1992","journal-title":"Aeq. Math."},{"issue":"4","key":"10.1016\/S0022-0000(03)00004-7_BIB18","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1090\/S0002-9939-1992-1059634-1","article-title":"On the behaviour of mappings which do not satisfy Hyers\u2013Ulam stability","volume":"114","author":"Hyers","year":"1992","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB19","unstructured":"D.E. Knuth, The Art of Computer Programming (3rd Edition), Vol. 2, Seminumerical Algorithms, Addison-Wesley, Reading, MA, 1998."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB20","doi-asserted-by":"crossref","unstructured":"R. Lipton, New Directions in Testing, Vol. 2. Series in Discrete Mathematics and Theoretical Computer Science, ACM\/AMS, New York, 1991, pp. 191\u2013202.","DOI":"10.1090\/dimacs\/002\/13"},{"key":"10.1016\/S0022-0000(03)00004-7_BIB21","doi-asserted-by":"crossref","unstructured":"F. Magniez, Multi-linearity self-testing with relative error, in: Proceedings of the 17th STACS, Lecture Notes in Computer Science, Vol. 1770, 2000, pp. 302\u2013313.","DOI":"10.1007\/3-540-46541-3_25"},{"issue":"2","key":"10.1016\/S0022-0000(03)00004-7_BIB22","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1090\/S0002-9939-1978-0507327-1","article-title":"On the stability of the linear mapping in Banach spaces","volume":"72","author":"Rassias","year":"1978","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB23","unstructured":"R. Rubinfeld, A mathematical theory of self-checking, self-testing and self-correcting programs, Ph.D. Thesis, University of California, Berkeley, 1990."},{"issue":"6","key":"10.1016\/S0022-0000(03)00004-7_BIB24","doi-asserted-by":"crossref","first-page":"1972","DOI":"10.1137\/S0097539796298625","article-title":"On the robustness of functional equations","volume":"28","author":"Rubinfeld","year":"1999","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB25","unstructured":"R. Rubinfeld, M. Sudan, Testing polynomial functions efficiently and over rational domains, in: Proceedings of the Third SODA, 1992, pp. 23\u201332."},{"issue":"2","key":"10.1016\/S0022-0000(03)00004-7_BIB26","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","article-title":"Robust characterizations of polynomials with applications to program testing","volume":"25","author":"Rubinfeld","year":"1996","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(03)00004-7_BIB27","first-page":"377","article-title":"Sull'approssimazione delle applicazioni localmente \u03b4-additive","volume":"117","author":"Skof","year":"1983","journal-title":"Atti Acad. Sci. Torino"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000047?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000047?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,18]],"date-time":"2020-03-18T12:36:40Z","timestamp":1584535000000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,3]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,3]]}},"alternative-id":["S0022000003000047"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00004-7","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,3]]}}}