Self-testing/correcting for polynomials and for approximate functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Self-testing/correcting for polynomials and for approximate functions

Source

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

New Orleans, Louisiana, United States

Pages: 33 - 42

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Peter Gemmell
Richard Lipton
Ronitt Rubinfeld
Madhu Sudan
Avi Wigderson

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 37

Additional Information:

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

CITED BY 37

	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
	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
	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
	Katalin Friedl , Zsolt Hátsági , Alexander Shen, Low-degree tests, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.57-64, January 23-25, 1994, Arlington, Virginia, United States
	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998
	Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR Lemma (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.537-546, May 01-04, 1999, Atlanta, Georgia, United States
	Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States
	Oded Goldreich , Dana Ron , Madhu Sudan, Chinese remaindering with errors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.225-234, May 01-04, 1999, Atlanta, Georgia, 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
	Uriel Feige , Carsten Lund, On the hardness of computing the permanent of random matrices (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.643-654, May 04-06, 1992, Victoria, British Columbia, Canada
	Wim van Dam , Frédéic Magniez , Michele Mosca , Miklos Santha, Self-testing of universal and fault-tolerant sets of quantum gates, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.688-696, May 21-23, 2000, Portland, Oregon, 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
	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
	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
	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
	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
	Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	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
	M. Kiwi, Algebraic testing and weight distributions of codes, Theoretical Computer Science, v.299 n.1-3, p.81-106, 18 April 2003
	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
	Funda Ergün , Ravi Kumar , Ronitt Rubinfeld, Fast approximate probabilistically checkable proofs, Information and Computation, v.189 n.2, p.135-159, March 15, 2004
	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
	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
	Eldar Fischer , Ilan Newman, Testing of matrix properties, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.286-295, July 2001, Hersonissos, Greece
	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
	Eldar Fischer , Ilan Newman , Jiří Sgall, Functions that have read-twice constant width branching programs are not necessarily testable, Random Structures & Algorithms, v.24 n.2, p.175-193, March 2004
	Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Journal of Computer and System Sciences, v.69 n.3, p.395-420, November 2004
	Johannes Köbler , Rainer Schuler, Average-case intractability vs. worst-case intractability, Information and Computation, v.190 n.1, p.1-17, April 10, 2004
	Zeev Dvir , Amir Shpilka, Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Oded Goldreich, Property testing in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	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
	Amit Deshpande , Rahul Jain , T. Kavitha , Satyanarayana V. Lokam , Jaikumar Radhakrishnan, Lower bounds for adaptive locally decodable codes, Random Structures & Algorithms, v.27 n.3, p.358-378, October 2005
	Manuel Blum , Hal Wasserman, Reflections on the Pentium Division Bug, IEEE Transactions on Computers, v.45 n.4, p.385-393, April 1996
	Oded Goldreich, A taxonomy of proof systems (part 2), ACM SIGACT News, v.25 n.1, p.22-30, March 1994
	Oded Goldreich, A taxonomy of proof systems (part 1), ACM SIGACT News, v.24 n.4, p.2-13, Dec. 1993
	Dana Ron, Property Testing: A Learning Theory Perspective, Foundations and Trends® in Machine Learning, v.1 n.3, p.307-402, March 2008
	Luca Trevisan, Guest column: additive combinatorics and theoretical computer science, ACM SIGACT News, v.40 n.2, June 2009