A parallel repetition theorem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A parallel repetition theorem

Full text

Pdf (867 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 447 - 456

Year of Publication: 1995

ISBN:0-89791-718-9

Author

Ran Raz

Weizmann Institute

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

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/225058.225181 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	N. Alon, "Probabilistic Methods in Extremal Finite Set Theory", Proc. of the Conference on Extremal Problems for Finite Sets, Hungary, 199i.
	2	S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, "Proof verification and intractability of approximation problems", FOG'S 92, lJ -23'.
	3	S. Arora, S. Safra, "Probabilistic Checking of Proofs; A New Characterization of NP", FOCS 9,?, 2-Is.
	4	L. Babai, L. Fortnow, C. Lund, "Non-Deterministic Ex-ponential Time has Two-Prover Interactive Protocols", FOCS 90, 16-25.
	5	M. Bellare, "Interactive proofs and approximation", ISTCS 93, 266-274.
	6	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]
	7	M. Bellare, P. Rogaway, "The complexity of approxi-mating a nonlinear program", In: Cornp/ezity in nu-merical optimization, P. Pardalos, cd., World Scientific, 1993.
	8	Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195129]
	9	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]
	10	Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Wigderson, Efficient identification schemes using two prover interactive proofs, Proceedings on Advances in cryptology, p.498-506, July 1989, Santa Barbara, California, United States
	11	Jin-yi Cai , Anne Condon , Richard J. Lipton, Playing games of incomplete information: 58, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.58-69, February 1990, Rouen, France
	12	Imre Csiszar , Janos G. Korner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, Inc., Orlando, FL, 1982
	13	Cynthia Dwork , Uriel Feige , Joe Kilian , Moni Naor , Muli Safra, Low Communication 2-Prover Zero-Knowledge Proofs for NP, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.215-227, August 16-20, 1992
	14	U. Feige, 'On the Success Probability of the Two Provers in One Round Proof Systems", Structures 91, 116-123.
	15	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]
	16	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]
	17	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]
	18	L. Fortnow, "Complexity-Theoretic Aspects of Interac-tive Proof Systems", Ph.D. Thesis, MIT/L CS\TR-447, 1989.
	19	L. Fortnow, J. Rompel, M. Sipser, "On the Power of Multi-Prover Interactive Protocols)), Structures 88, 156-161.
	20	L. Fortnow, J. Rompel, M. Sipser, "Errata for On the Power of Multi-Prover Interactive Protocols", Struc-tures 90, 318-319.
	21	Robert M. Gray, Entropy and information theory, Springer-Verlag New York, Inc., New York, NY, 1990
	22	B. Kalyanasundaram, G. Schnitger, "The probabilktic communication complexity of set intersection", Struc-tures 87, 41-49.
	23	J. Kilian, "Strong Separation Models of Multi Prover Interactive Proofs" DIMA CS Workshop on Cryptogra-phy, October 1990.
	24	Dror Lapidot , Adi Shamir, A One-Round, Two-Prover, Zero-Knowledge Protocol for NP, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.213-224, August 11-15, 1991
	25	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]
	26	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]
	27	D. Peleg, "On the Maximal Number of Ones in Zero-One Matrices with No Forbidden Rectangles", manuscript, 1990.
	28	A. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, v.106 n.2, p.385-390, Dec. 1992 [doi>10.1016/0304-3975(92)90260-M]
	29	G. Tardos. "Multi-prover encoding schemes, and 3- prover interactive proofs." Structures, 1994.
	30	0. Verbitsky, "Towards the Parallel Repetition Conjec-ture", Structures, 1994.
	31	0. Verbitsky, "The Parallel Repetition Conjecture for Trees is True", manuscript, 1994.

CITED BY 17

	Luca Trevisan, Recycling queries in PCPs and in linearity tests (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.299-308, May 24-26, 1998, Dallas, Texas, United States
	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
	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
	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
	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
	Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States
	Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	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
	Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998
	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
	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
	Hoong Chuin Lau , Osamu Watanabe, Randomized approximations of the constraint satisfaction problem, Nordic Journal of Computing, v.3 n.4, p.405-424, Winter 1996
	Itzhak Parnafes , Ran Raz , Avi Wigderson, Direct product results and the GCD problem, in old and new communication models, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.363-372, May 04-06, 1997, El Paso, Texas, United States
	Giovanni Di Crescenzo, Sharing one secret vs. sharing many secrets, Theoretical Computer Science, v.295 n.1-3, p.123-140, 24 February 2003
	Nader H. Bshouty , Lynn Burroughs, Maximizing agreements and coagnostic learning, Theoretical Computer Science, v.350 n.1, p.24-39, 18 January 2006
	David S. Johnson, The NP-completeness column: The many limits on approximation, ACM Transactions on Algorithms (TALG), v.2 n.3, p.473-489, July 2006
	Rafael Pass , Muthuramakrishnan Venkitasubramaniam, An efficient parallel repetition theorem for Arthur-Merlin games, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA