Self-testing/correcting with applications to numerical problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Self-testing/correcting with applications to numerical problems

Full text

Pdf (951 KB)

Source

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

Baltimore, Maryland, United States

Pages: 73 - 83

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

M. Blum	Computer Science Division, U.C. Berkeley, Berkeley, California
M. Luby	International Computer Science Institute, Berkeley, California
R. Rubinfeld	Computer Science Division, U.C. Berkeley, Berkeley, California

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 75, Citation Count: 31

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/100216.100225 What is a DOI?

Warning: The download time has expired please click on the item to try again.

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	Leonard M. Adleman , Ming-Deh Huang , Kireeti Kompella, Efficient checkers for number-theoretic computations, Information and Computation, v.121 n.1, p.93-102, Aug. 15, 1995 [doi>10.1006/inco.1995.1125]
	2	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
	3	Ben-Or, M., Coppersmith, D., Luby, M., Rubinfeld, R., "Convolutions on Groups", rough manuscript.
	4	Blum, M., "Designing programs to check their work", Submitted to CACM.
	5	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]
	6	Blum, M., Luby, M., Rubinfeld, R., "Program Result Checking Against Adaptive Programs and in Cryptographic Settings", DIMA CS workshop on cryptography and distributed systems, 1989.
	7	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	8	Feigenbaum, J., Kannan, S., Nisan, N., "Lower Bounds on Random-Self-Reducibility", Structures in Complexity Theory, 1990.
	9	Freivalds, R., "Fast Probabilistic Algorithms", Springer Verlag Lecture Notes in CS No. 74, Mathematical Foundations of CS, 57-69 (1979).
	10	Michael Kaminski, A note on probabilistically verifying integer and polynomial products, Journal of the ACM (JACM), v.36 n.1, p.142-149, Jan. 1989 [doi>10.1145/58562.214082]
	11	Kannan, S., "Program Result Checking with Applications", Ph.D. thesis, U.C. Berkeley, 1990.
	12	Lipton, R., "New directions in testing", manuscript.
	13	Randall, D., "Efficient Random Generation of Invertible Matrices", personal communication.
	14	Rubinfeld, R., "Designing Checkers for Programs that Run in Parallel", manuscript, 1989.
	15	Rubinfeld, R. "Batch Checking for the Mod Function", manuscript, 1990.
	16	A. C.-C. Yao, Coherent functions and program checkers, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.84-94, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100226]

CITED BY 31

	Sigal Ar , Jin-Yi Cai, Reliable benchmarks using numerical instability, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.34-43, January 23-25, 1994, Arlington, Virginia, United States
	Kurt Mehlhorn , Michael Müller , Stefan Näher , Stefan Schirra , Michael Seel , Christian Uhrig , Joachim Ziegler, A computational basis for higher-dimensional computational geometry and applications, Proceedings of the thirteenth annual symposium on Computational geometry, p.254-263, June 04-06, 1997, Nice, France
	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
	B. Ravikumar, A note on checking matrix products (extended abstract), Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.937-943, March 1992, Kansas City, Missouri, United States
	J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, Testing and spot-checking of data streams (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.165-174, January 09-11, 2000, San Francisco, California, United States
	Dana Randall , Alistair Sinclair, Testable algorithms for self-avoiding walks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.593-602, January 23-25, 1994, Arlington, Virginia, United States
	M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States
	Luca Trevisan, Recycling queries in PCPs and in linearity tests (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.299-308, May 24-26, 1998, Dallas, Texas, United States
	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
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States
	Manuel Blum , Sampath Kannan, Designing programs that check their work, Journal of the ACM (JACM), v.42 n.1, p.269-291, Jan. 1995
	Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998
	Phillip B. Gibbons , John L. Bruno , Steven Phillips, Post-mortem black-box correctness tests for basic parallel data structures, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.44-53, June 27-30, 1999, Saint Malo, France
	Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada
	Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992
	Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States
	László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, 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
	Alexander Polishchuk , Daniel A. Spielman, Nearly-linear size holographic proofs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.194-203, May 23-25, 1994, Montreal, Quebec, Canada
	Koen Claessen , John Hughes, QuickCheck: a lightweight tool for random testing of Haskell programs, ACM SIGPLAN Notices, v.35 n.9, p.268-279, Sept. 2000
	Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States
	Dwight S. Wilson , Gregory F. Sullivan , Gerald M. Masson, Certification of Computational Results, IEEE Transactions on Computers, v.44 n.7, p.833-847, July 1995
	Shlomi Dolev , Frank Stomp, Safety assurance via on-line monitoring, Distributed Computing, v.16 n.4, p.269-277, December 2003
	Craig Gentry , Zulfikar Ramzan , Stuart Stubblebine, Secure distributed human computation, Proceedings of the 6th ACM conference on Electronic commerce, p.155-164, June 05-08, 2005, Vancouver, BC, Canada
	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
	Irit Dinur , Shmuel Safra, The importance of being biased, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Kurt Mehlhorn , Stefan Näher , Thomas Schilz , Stefan Schirra , Michael Seel , Raimund Seidel , Christian Uhrig, Checking geometric programs or verification of geometric structures, Proceedings of the twelfth annual symposium on Computational geometry, p.159-165, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	V. Rödl , M. Schacht, Property testing in hypergraphs and the removal lemma, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Oded Goldreich, A taxonomy of proof systems (part 2), ACM SIGACT News, v.25 n.1, p.22-30, March 1994
	Michael Saks , C. Seshadhri, Parallel monotonicity reconstruction, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.962-971, January 20-22, 2008, San Francisco, California