PCPs with small soundness error

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

PCPs with small soundness error

Full text

Pdf (1.95 MB)

Source

ACM SIGACT News archive
Volume 39 , Issue 3 (September 2008) table of contents

COLUMN: Technical columns table of contents

Pages 41-57

Year of Publication: 2008

ISSN:0163-5700

Author

Irit Dinur

Weizmann Institute of Science, Rehovot, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 39, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/1412700.1412713 What is a DOI?

ABSTRACT

The soundness error of a PCP verifier is the probability (usually denoted ε) that the verifier accepts an incorrect input. We are interested in the smallest possible values of ε for which the PCP theorem holds, and in particular whether the theorem holds when ε is an inverse polynomial function of the input length. We discuss the 'sliding scale conjecture' of [BGLR93, LY94] and related questions. We then sketch some of the existing approaches and constructions of PCPs with sub-constant soundness error.

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	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 [doi>10.1145/278298.278306]
	2	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]
	3	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 [doi>10.1145/273865.273901]
	4	Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding, SIAM Journal on Computing, v.36 n.4, p.889-974, December 2006 [doi>10.1137/S0097539705446810]
	5	M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient multi-prover interactive proofs with applications to approximation problems. In Proc. 25th ACM Symp. on Theory of Computing, pages 113--131, 1993.
	6	Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
	7	A. Bogdanov. Gap amplification fails below 1/2. Comment on ECCC TR05-046, can be found at http://eccc.uni-trier.de/eccc-reports/2005/TR05-046/commt01.pdf, 2005.
	8	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 [doi>10.1145/301250.301265]
	9	Irit Dinur, The PCP theorem by gap amplification, Journal of the ACM (JACM), v.54 n.3, p.12-es, June 2007 [doi>10.1145/1236457.1236459]
	10	Irit Dinur , Omer Reingold, Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem, SIAM Journal on Computing, v.36 n.4, p.975-1024, December 2006 [doi>10.1137/S0097539705446962]
	11	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]
	12	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]
	13	Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
	14	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]
	15	D. Moshkovitz and R. Raz. Two query PCP with sub-constant error. In Proc. 49th IEEE Symp. on Foundations of Computer Science, 2008. To appear.
	16	Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
	17	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]
	18	Gábor Tardos, Multi-prover encoding schemes and three-prover proof systems, Journal of Computer and System Sciences, v.53 n.2, p.251-260, Oct. 1996 [doi>10.1006/jcss.1996.0066]