Spot-checkers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Spot-checkers

Full text

Pdf (1.33 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 259 - 268

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Funda Ergün	Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA
Sampath Kannan	Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA
S. Ravi Kumar	IBM Almaden Research Center, San Jose, CA
Ronitt Rubinfeld	Department of Computer Science, Cornell University, Ithaca, NY
Mahesh Viswanathan	Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 23, Citation Count: 16

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/276698.276757 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.

	Acz66	J. Aczel. Lectures on Functional Equations and their Applications. Academic Press, 1966.
	AHK95	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]
	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, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. Proc. 33rd Foundations of Computer Science, pp. 14--23, 1992.
	AS92	S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. Proc. 33rd Foundations of Computer Science, pp. 2-13, 1992.
	BGR96	Mihir Bellare , Juan A. Garay , Tal Rabin, Batch Verification with Applications to Cryptography and Checking, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.170-191, April 20-24, 1998
	BEG+91	Manuel Blum , Will Evans , Peter Gemmell , Sampath Kannan , Moni Naor, Checking the correctness of memories, Proceedings of the 32nd annual symposium on Foundations of computer science, p.90-99, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185352]
	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]
	BLR93	Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
	BW94	M. Blum and H. Wasserman. Program resultchecking: A theory of testing meets a test of theory. Proc. 35th Foundations of Computer Science, pp. 382- 392, 1994.
	BW94	M. Blum and H. Wasserman. Reflections on the Pentium division bug. Proc. 8th Intl. Software Quality It~ek, 1994.
	CR92	E. Castillo and M.R. Ruiz-Cobo. Functional Equations and Modeling in Science and Engineering. Marcel Dekker Inc., 1992.
	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
	EKS97	F. Ergiin, S. Ravi Kumar, and D. Sivakumar. Selftesting without the generator bottleneck, sicomp, to appear.
	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]
	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
	GR97	Oded Goldreich , Dana Ron, Property testing in bounded degree graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.406-415, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258627]
	Kan90	S. Kannan. Program Result Checking with Applications. PhD thesis, U. of California at Berkeley, 1990.
	KR98	S. Ravi Kumar and R. Rubinfeld. Testing Abelian Group Operations. Manuscript.
	KS96	S. R. Kumar, Efficient self-testing/self-correction of linear recurrences, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.602, October 14-16, 1996
	Lip91	R. Lipton. New directions in testing. Proc. i)I- MACS $ibr 'kshop on Distr. Comp. and Cryptography, pp. 191-202, 1991.
	Rub94	R. Rubinfeld. Robust functional equations with applications to self-testing/correcting. Proc. 35th Fottndations of Computer Science, pp. 288-299, 1994.
	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]
	RaS96	S. Rajagopalan , L. J. Schulman, Verifying identities, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.612, October 14-16, 1996
	Vai93	Feodor Vainstein, Algebraic methods in hardware/software testing, Boston University, Boston, MA, 1992

CITED BY 16

	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
	Funda Ergün , Ravi Kumar , Ronitt Rubinfeld, Fast approximate PCPs, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.41-50, May 01-04, 1999, Atlanta, Georgia, United States
	Michal Parnas , Dana Ron, Testing metric properties, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.276-285, July 2001, Hersonissos, Greece
	Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998
	Michael A. Bender , Dana Ron, Testing properties of directed graphs: acyclicity and connectivity, Random Structures & Algorithms, v.20 n.2, p.184-205, March 2002
	Bernard Chazelle , Ding Liu , Avner Magen, Sublinear geometric algorithms, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	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
	Christian S. Collberg , Clark Thomborson, Watermarking, tamper-proffing, and obfuscation: tools for software protection, IEEE Transactions on Software Engineering, v.28 n.8, p.735-746, August 2002
	Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States
	Taejoon Park , Kang G. Shin, Soft Tamper-Proofing via Program Integrity Verification in Wireless Sensor Networks, IEEE Transactions on Mobile Computing, v.4 n.3, p.297-309, May 2005
	Oded Goldreich, Property testing in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Nir Ailon , Bernard Chazelle , Seshadhri Comandur , Ding Liu, Estimating the distance to a monotone function, Random Structures & Algorithms, v.31 n.3, p.371-383, October 2007
	Bernard Chazelle , C. Seshadhri, Online geometric reconstruction, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Nir Ailon , Bernard Chazelle, Information theory in property testing and monotonicity testing in higher dimension, Information and Computation, v.204 n.11, p.1704-1717, November 2006
	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
	Hong-Yiu Lin , Yuh-Dauh Lyuu , Tak-Man Ma , Yen-Wu Ti, Testing whether a digraph contains H-free k-induced subgraphs, Theoretical Computer Science, v.407 n.1-3, p.545-553, November, 2008