Approximate testing with relative error

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate testing with relative error

Full text

Pdf (832 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 51 - 60

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Marcos Kiwi	Dept. de Ing. Matemática, U. de Chile, Santiago 170-3, Chile
Frédéric Magniez	Université Parie-Sud, 91405 Orsay, France
Miklos Santha	CNRS, URA 410, Université Paris-Sud, 91405 Orsay, France

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 18, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301269 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AB83	M. Albert and J. Baker. Functions with bounded nth difference. Ann. ?olonici Mathematici, 43:93- t03, 1983.
	ABC+93	S. Ar , M. Blum , B. Codenotti , P. Gemmell, Checking approximate computations over the reals, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.786-795, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167288]
	ALM+92	S. Arora, G. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proc. 33rd FOGS, pp. 14-23, 1992.
	BF90	Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
	BK89	M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
	BLR90	M. Blum , M. Luby , R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.73-83, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100225]
	Blu88	M. Blum. Designing programs to check their work. Technical F/.eport TR-88-009, ICSI, 1988.
	BW94	M. B!um and H. Wasserman. Program resultchecking: A theory of testing meets a test of theory. In Proc. 35th FOGS, pp. 382-392, 1994.
	Cop89	D. Coppersmith. Manuscript. See discussion in {BLR90}, December 1989.
	EKR96	F. Ergun , S. R. Kumar, Approximate checking of polynomials and functional equations, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.592, October 14-16, 1996
	For95	G.L. Forti. Hyers-Ulam stability of functional equations in several variables. Aeq. Mathematicae, 50:143- 190, 1995.
	Gaj90	Z. Gajda. Local stability of the functional equation characterizing polynomial functions. Ann. PoIonici Mathemtici, 42:119-137, 1990.
	GGR96	O. Goldreich , S. Goldwasser , D. Ron, Property testing and its connection to learning and approximation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.339, October 14-16, 1996
	GLR+91	Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
	HR92	D.H. Hyers and T. M. Rassias. Approximate homomorphisms. Aeq. Mathematicae, 44:125-153, 1992.
	HS92	D.H. Hyers and P. ~emrl. On the behaviour of mappings which do not satisfy Hyers-U!am stability. Proc. American Mathematical Society, 114(4):989- 993, April 1992.
	Hye41	D.H. Hyers. On the stability of the linear functional equation. Proc. of the National Academy of Science, U.S.A., 27:222-224, 1941.
	Knu98	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	Lip91	Ft. Lipton. New directions in testingt Vot. 2 of Series in Discrete Mathematics and Theoretical Computer Science, pp. 191-202. ACM/AMS, 1991.
	Ras78	T.M. Rassias. On the stability of the linear mapping in Banach spaces. Proc. of the American Mathematical Society, 72(2):297-300, November 1978.
	RS92	Ronitt Rubinfeld , Madhu Sudan, Self-testing polynomial functions efficiently and over rational domains, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.23-32, September 1992, Orlando, Florida, United States
	RS96	Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
	Rub90	Ronitt A. Rubinfeld, A mathematical theory of self-checking, self-testing and self-correcting programs, University of California at Berkeley, Berkeley, CA, 1991
	Rub94	Ft. Rubinfeld. On the robustness of functional equations. In Proc. 35th FOG'S, pp. 288-299, 1994.
	Sko83	F. Skof. Sull'approssimazione delle appticazioni localmente S-additive. Atti della Accademia delIe Sciencze di Torino, 117:377-389, 1983. (In Italian.)

CITED BY 2

	Cécile Germain-Renaud , Nathalie Playez, Result checking in global computing systems, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
	Marcos Kiwi , Frédéric Magniez , Miklos Santha, Exact and approximate testing/correcting of algebraic functions: a survey, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002