Checking approximate computations over the reals

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Checking approximate computations over the reals

Full text

Pdf (847 KB)

Source

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

San Diego, California, United States

Pages: 786 - 795

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

S. Ar
M. Blum
B. Codenotti
P. Gemmell

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 13, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/167088.167288 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.

	1	P#. Beigel. Personal communication to Manuel Blum; see {2}.
	2	M. Blum. Designing Programs to Check their Work. ICSI TR-88-009, 1988.
	3	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]
	4	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]
	5	R. Cleve, M. Luby. A Note on Self- Testing/Correcting Methods for Trigonometric Functions. ICSI TR-90-032, July 1990.
	6	D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
	7	R. Freivalds. Fast probabilistic algorithms. Springer Verlag Lecture Notes in CS, Vol. 7q}, 57- 69, 1979.
	8	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]
	9	G. H. Golub and C. F. van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, Md, 1983.
	10	S. Kannan. Program Checkers for Algebraic Problems. ICSI TR-89-064, 1989.
	11	R. Kannan , A. K. Lenstra , L. Lovász, Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.191-200, December 1984 [doi>10.1145/800057.808681]
	12	R. Lipton. New Directions in Testing. In Distrib. Comput. and Cryptography, DIMACS Series on Discrete Mathematzcs and Theoretical Computer Sczence, pages 191-202, 1991.
	13	D. Randall. Efficient random Generation of Invertible Matrices. personal communication.
	14	Ronitt A. Rubinfeld, A mathematical theory of self-checking, self-testing and self-correcting programs, University of California at Berkeley, Berkeley, CA, 1991

CITED BY 9

	Funda Ergün, Testing multivariate linear functions: overcoming the generator bottleneck, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.407-416, May 29-June 01, 1995, Las Vegas, Nevada, United States
	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
	Manuel Blum , Hal Wasserman, Reflections on the Pentium Division Bug, IEEE Transactions on Computers, v.45 n.4, p.385-393, April 1996
	Marcos Kiwi , Frédéric Magniez , Miklos Santha, Approximate testing with error relative to input size, Journal of Computer and System Sciences, v.66 n.2, p.371-392, March 2003
	Hal Wasserman , Manuel Blum, Software reliability via run-time result-checking, Journal of the ACM (JACM), v.44 n.6, p.826-849, Nov. 1997
	Peifeng Hu , Zhenyu Zhang , W. K. Chan , T. H. Tse, An empirical comparison between direct and indirect test result checking approaches, Proceedings of the 3rd international workshop on Software quality assurance, November 06-06, 2006, Portland, Oregon
	Marcos Kiwi , Frédéric Magniez , Miklos Santha, Approximate testing with relative error, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.51-60, May 01-04, 1999, Atlanta, Georgia, United States
	Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation, Journal of the ACM (JACM), v.53 n.3, p.307-323, May 2006
	Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.259-268, May 24-26, 1998, Dallas, Texas, United States