Two prover protocols

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Two prover protocols: low error at affordable rates

Full text

Pdf (1.15 MB)

Source

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

Montreal, Quebec, Canada

Pages: 172 - 183

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Uri Feige	Dept. of Applied Math., The Weizmann Institute, Rehovot, Israel
Joe Kilian	NEC Research Institute, 4 Independence Way, Princeton, New Jersey

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 17, 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/195058.195128 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, 1991.
	2	S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, "Proof verification and intractability of approximation problems", FOCS 92, I#-~3.
	3	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]
	4	L. Babai, L. Fortnow, C. Lund, "Non-Deterministic Exponential 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 approximating a nonlinear program", In: Complexity in numerical optimizatzon, P. Pardalos, ed., 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	Piotr Berman , Georg Schnitger, On the complexity of approximating the independent set problem, Information and Computation, v.96 n.1, p.77-94, Jan. 1992 [doi>10.1016/0890-5401(92)90056-L]
	12	J. Cai, A. Condon, R. Lipton, "On Bounded Round Multi-Prover Interactive Proof Systems", Structures 90, 45-54.
	13	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
	14	J. Ca.i, A. Condon, R. Lipton, "PSPACE is Provable by Two Provers in One Round", Structures 91, 110-I 15.
	15	H. Chernoff, "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations", Annals of Math. Star., 23:493-509, 1952.
	16	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
	17	U. Feige, "On the Success Probability of the Two Provers in One Round Proof Systems", Structures 91, 116-123.
	18	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]
	19	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]
	20	U. Feige, M. Szegedy, unwritten manuscript.
	21	L. Fortnow, J. Rompel, M. Sipser, "On the Power of Multi-Prover Interactive Protocols", Structures 88, 156-161.
	22	L. Fortnow, J. Rompel, M. Sipser, "Errata for On the Power of Multi-Prover Interactive Protocols", Structures 90, 318-319.
	23	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]
	24	J. Kilian, "Strong Separation Models of Multi Prover Interactive Proofs" DIMA CS Workshop on Cryptography, October 1990.
	25	J. Kilian, M. Naor, "On the complexity of statistical reasoning", manuscript.
	26	Daphne Koller , Nimrod Megiddo, Constructing small sample spaces satisfying given constraints, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.268-277, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167168]
	27	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
	28	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]
	29	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	30	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]
	31	D. Peleg, "On the Maximal Number of Ones in Zero-One Matrices with No Forbidden Rectangles", manuscript, 1990.
	32	L. Roniger, M. Feige, "From Pioneer to Freier: the Changing Models of Generalized Exchange in Israel", European Journal of Sociology, 1992, 33(2), 280-307.
	33	G. Tardos. "Multi-prover encoding schemes, and 3- prover interactive proofs." Structures, 199#.
	34	O. Verbitsky, "Towards the Parallel Repetition Conjecture", Structures, 199#.

CITED BY 10

	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
	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
	William Aiello , Mihir Bellare , Ramarathnam Venkatesan, Knowledge on the average—perfect, statistical and logarithmic, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.469-478, May 29-June 01, 1995, Las Vegas, Nevada, 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
	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
	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
	M. Bellare , S. Goldwasser , C. Lund , A. Russell, Efficient probabilistic checkable proofs and applications to approximation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.820, May 23-25, 1994, Montreal, Quebec, Canada
	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
	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
	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