A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP

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.

	ALM+92	S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proc. 33rd IEEE Syrup. on Foundations of Computer Science, pages 13-22, 1992.
	AS92	S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. In Proc. 33rd IEEE Syrup. on Foundations of Computer Science, pages 2-13, 1992.
	AS97	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 [doi>10.1145/258533.258642]
	Bab85	L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
	BFL91	L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3-40, 1991.
	BGKW88	Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
	BGLR93	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]
	BGS95	M. Bellare, O. Goldreich, and M. Sudan. Free bits and nonapproximability. In Proc. 27th A CM Symp. on Theory of Computing, 1995.
	BLR90	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]
	Coo71	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	FGL+91	U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
	FL92	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]
	FS91	K. Friedl and M. Sudan. Some improvements to lowdegree-tests. In Proc. of the Third Israel Symposium on Theory of Computing, ACM 1991.
	FSH94	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
	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]
	GMR89	S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
	GS	O. Goldreich and S .Safra. A Combinatorial Consistency Lemma with application to the PCP Theorem. Electronic Colloquium on Computational Complexity (ECUC), TR96-047.
	Hås96a	Johan Håstad, Testing of the long code and hardness for clique, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.11-19, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237820]
	Hås96b	J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
	Hås97	Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
	KLS93	S. Khanna, N. Linial, and S. Safra. On the hardness of approximating the chromatic number. In Proceedings of the ~nd Israel Symposium on Theory and Computing Systems, ISTCS, pages 250-260. IEEE Computer Society Press, 1993.
	LFKN92	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]
	Lip91	R. Lipton. New directions in testing. In J. Feigenbaum and M. Merritt, editors, Distributed Computing and Crypt ography. American Mathematical Society, 1991. Dimacs Series in Discrete Mathematics and Theoretical Computer Science, volume 2.
	LS91	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]
	LY94	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
	PY91	C. Papadimitriou and M. Yann~s. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425-440, 1991.
	Ra95	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]
	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
	Rub90	Ronitt A. Rubinfeld, A mathematical theory of self-checking, self-testing and self-correcting programs, University of California at Berkeley, Berkeley, CA, 1991
	Sha92	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	She91	A. Shen. Multilinearity test made easy. Manuscript, 1991.
	Sud92	Madhu Sudan, Efficient checking of polynomials and proofs and the hardness of approximation problems, University of California at Berkeley, Berkeley, CA, 1992