Improved low-degree testing and its applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved low-degree testing and its applications

Full text

Pdf (1.62 MB)

Source

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

El Paso, Texas, United States

Pages: 485 - 495

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Sanjeev Arora	Princeton University
Madhu Sudan	IBM T. J. Watson Research Center, P.O.Box 218, Yorktown Heights, NY

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): 17, Citation Count: 28

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/258533.258642 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	S. AR, R. LIPTON, R. RUBINFELD AND M. SUDAN. Reconstructing algebraic functions from noisy data. IEEE FOCS 1992.
	2	S. ARORA Unpublished, 1993.
	3	Sanjeev Arora, Probabilistic checking of proofs and hardness of approximation problems, University of California at Berkeley, Berkeley, CA, 1995
	4	S. ARORA, L. BABAI, J. STERN AND Z. SWEEDYK. The hardness of approximating problems defined by linear constraints. IEEE FOCS 1993.
	5	S. ARORA, C. LUND, R. MOTWANI, M. SUDAN AND M. SZEGEDY. Proof verification and the hardness of approximation problems. IEEE FOCS 1992.
	6	S. ARORA AND S. SAFRA. Probabilistic checking of proofs: a new characterization of NP. IEEE FOCS 1992.
	7	L. BABAI, L. FORTNOW, AND C. LUND. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3--40, 1991.
	8	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 [doi>10.1145/103418.103428]
	9	M. Bellare , O. Goldreich , M. Sudan, Free bits, PCPs and non-approximability-towards tight results, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.422, October 23-25, 1995
	10	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 [doi>10.1145/167088.167174]
	11	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]
	12	U. FEIGE. A threshold of In n for Set Cover. ACM STOC 1996.
	13	Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
	14	Uri Feige , Joe Kilian, Two prover protocols: low error at affordable rates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.172-183, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195128]
	15	Uriel Feige , Joe Kilian, Impossibility results for recycling random bits in two-prover proof systems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.457-468, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225183]
	16	Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
	17	Some improvements to total degree tests, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.190, January 04-06, 1995
	18	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]
	19	O. Goldreich , R. Rubinfeld , M. Sudan, Learning polynomials with queries: The highly noisy case, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.294, October 23-25, 1995
	20	E. KALTOFEN. Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM Journal on Computing, 14(2):469-489, 1985.
	21	E. KALTOFEN. Effective Hilbert irreducibility. Information and Control, 66:123-137, 1985.
	22	Erich Kaltofen, Effective Noether irreducibility forms and applications, Journal of Computer and System Sciences, v.50 n.2, p.274-295, April 1995
	23	Dror Lapidot , Adi Shamir, Fully parallelized multi prover protocols for NEXP-time (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.13-18, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185342]
	24	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 [doi>10.1145/146585.146605]
	25	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
	26	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 [doi>10.1145/195058.195132]
	27	Ran Raz, A parallel repetition theorem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.447-456, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225181]
	28	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 [doi>10.1145/258533.258641]
	29	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]
	30	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	31	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	32	V. Ponnampalam , B. Vucetic, Maximum likelihood decoding of Reed Solomon codes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.164, October 14-16, 1996
	33	G. T^RDOS. Personal Communication, 1993.
	34	G. TARDOS. Multi-prover encoding schemes and threeprover proof systems. Proceech'ngs of the 9th Annual Conference on Structure in Complexity Theory, IEEE, 1994.
	35	G. TARDOS. Personal Communication, 1996.

CITED BY 28

	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, 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
	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
	Igor E. Shparlinski, Sparse polynomial approximation in finite fields, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.209-215, July 2001, Hersonissos, Greece
	Irit Dinur , Eldar Fischer , Guy Kindler , Ran Raz , Shmuel Safra, PCP characterizations of NP: towards a polynomially-small error-probability, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.29-40, May 01-04, 1999, Atlanta, Georgia, United States
	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
	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
	Erich Kaltofen, Polynomial factorization: a success story, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.3-4, August 03-06, 2003, Philadelphia, PA, USA
	Yevgeniy Dodis , Sanjeev Khanna, Design networks with bounded pairwise distance, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.750-759, May 01-04, 1999, Atlanta, Georgia, United States
	Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, 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
	Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Lap Mui Ann Chan , Ana Muriel , Zuo-Jun Max Shen , David Simchi-Levi , Chung-Piaw Teo, Effective Zero-Inventory-Ordering Policies for the Single-Warehouse Multiretailer Problem with Piecewise Linear Cost Structures, Management Science, v.48 n.11, p.1446-1460, November 2002
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 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
	R. Ravi , A. Sinha, Multicommodity facility location, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Eduardo S. Laber , Loana Tito Nogueira, On the hardness of the minimum height decision tree problem, Discrete Applied Mathematics, v.144 n.1-2, p.209-212, 30 November 2004
	Stephan Eidenbenz, Approximation algorithms for terrain guarding, Information Processing Letters, v.82 n.2, p.99-105, 30 April 2002
	Jonas Holmerin , Subhash Khot, A new PCP outer verifier with applications to homogeneous linear equations and max-bisection, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems, Information and Computation, v.173 n.1, p.40-63, February 25, 2002
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, v.13 n.1/2, p.1-46, January 2004
	Eli Ben-Sasson , Madhu Sudan, Robust locally testable codes and products of codes, Random Structures & Algorithms, v.28 n.4, p.387-402, July 2006
	Noga Alon , Dana Moshkovitz , Shmuel Safra, Algorithmic construction of sets for k-restrictions, ACM Transactions on Algorithms (TALG), v.2 n.2, p.153-177, April 2006
	Maria Serna , Luca Trevisan , Fatos Xhafa, The approximability of non-Boolean satisfiability problems and restricted integer programming, Theoretical Computer Science, v.332 n.1-3, p.123-139, 28 February 2005
	Zhen Liu , Srinivasan Parthasarthy , Anand Ranganathan , Hao Yang, Scalable event matching for overlapping subscriptions in pub/sub systems, Proceedings of the 2007 inaugural international conference on Distributed event-based systems, June 20-22, 2007, Toronto, Ontario, Canada
	Irit Dinur, PCPs with small soundness error, ACM SIGACT News, v.39 n.3, September 2008
	Dana Ron, Property Testing: A Learning Theory Perspective, Foundations and Trends® in Machine Learning, v.1 n.3, p.307-402, March 2008