PCP characterizations of NP

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

PCP characterizations of NP: towards a polynomially-small error-probability

Full text

Pdf (952 KB)

Source

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

Atlanta, Georgia, United States

Pages: 29 - 40

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Irit Dinur	School of Mathematical Sciences, Tel Aviv University, Israel
Eldar Fischer	School of Mathematical Sciences, Tel Aviv University, Israel
Guy Kindler	School of Mathematical Sciences, Tel Aviv University, Israel
Ran Raz	Weismann Inst. of Science, Israel
Shmuel Safra	School of Mathematical Sciences, Tel Aviv University, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 10

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

	ABMP98	M. Alekhnovich, S. Buss, S. Moran, and T. Pitassi. Minimum propositional proof length is NP~hard to linearly approximate. Manuscript, 1998.
	ALM+92	S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractabilit.y of approximation problems. In Proc. $$rd IEEE S!/mp. 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. 3$rd IEEE Syrnp. 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]
	BFL91	L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3-40, 199t.
	BGLR93	M. Bells.re, S. Goldwasser, C. Lund, and A. Russell. Efficient multi-prover interactive proofs with applications to approximation problems. In Proc. l~Sth A CM Syrup. on Theory of Computing, pages 113-131, 1993.
	DS98	I. Dinur and S. Safra. Monotone-minimumsatisfying assignment is NP-hard for almost polynomial factors. Manuscript, 1998.
	HPS93	Johan Håstad , Steven Phillips , Shmuel Safra, A well-characterized approximation problem, Information Processing Letters, v.47 n.6, p.301-305, Oct. 18, 1993 [doi>10.1016/0020-0190(93)90076-L]
	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]
	Raz98	Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
	RS97	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]

CITED BY 10

	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
	Irit Dinur , Shmuel Safra, On the hardness of approximating label-cover, Information Processing Letters, v.89 n.5, p.247-254, 16 March 2004
	Eldar Fischer , Guy Kindler , Dana Ron , Shmuel Safra , Alex Samorodnitsky, Testing juntas, Journal of Computer and System Sciences, v.68 n.4, p.753-787, June 2004
	Eli Ben-Sasson , Madhu Sudan, Simple PCPs with poly-log rate and query complexity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	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
	Dana Moshkovitz , Ran Raz, Sub-constant error low degree test of almost-linear size, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Julia Chuzhoy , Sanjeev Khanna, Polynomial flow-cut gaps and hardness of directed cut problems, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Oded Goldreich, Probabilistic Proof Systems: A Primer, Foundations and Trends® in Theoretical Computer Science, v.3 n.1, p.1-91, January 2008
	Irit Dinur, PCPs with small soundness error, ACM SIGACT News, v.39 n.3, September 2008
	Julia Chuzhoy , Sanjeev Khanna, Polynomial flow-cut gaps and hardness of directed cut problems, Journal of the ACM (JACM), v.56 n.2, p.1-28, April 2009