Uriel Feige
ABSTRACT
We characterize the power of two-prover one-round (MIP(2,1)) proof systems, showing that MIP(2,1)=NEXPTIME. However, the following intriguing question remains open: Does parallel repetition decrease the error probability of MIP(2,1) proof systems?.
We use techniques based on quadratic programming to study this problem, and prove the parallel repetition conjecture in some special cases. Interestingly, our work leads to a general polynomial time heuristic for any NP-problem. We prove the effectiveness of this heuristic for several problems, such as computing the chromatic number of perfect graphs.
- 1.R. Aleliunas, R. Karp, R. Lipton, L. Lov~sz, C. Rackoff, "Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems", 20th FOGS, 1979, pp. #18-2123.Google Scholar
- 2.N. Alon, "Probabilistic Methods in Extremal Finite Set Theory", to appear in the Proc. o/ the Conference on Eztremal Pro61ems for Finite Sets, Hun#lar#, 1991.Google Scholar
- 3.L. Babai, L. Fortnow, C. Lund, "Non- Deterministic Exponential Time has Two-Prover interactive Protocols", 31st FOGS, 1990, pp. 16- 25.Google Scholar
- 4.M. Beilare, P. Rogaway, "The Complexity of Continuous Optimization , manuscript.Google Scholar
- 5.M. Ben-or, S. Goldwasser, J. Kilian, A. Wigderson, "Multi Prover Interactive Proofs: How to Remove Intractability", 20th STOC, i988, pp. 113-171. Google ScholarDigital Library
- 6.Boros and Hammer.Google Scholar
- 7.J. CaJ, A. Condos, R. Lipton, "On Bounded Round Multi-Prover Interactive Proof Systems", Structures 1990, pp.15-94.Google Scholar
- 8.J. Cai, A. Condos, R. Lipton, "Playing Games of Incomplete Information", STA C8 1990. Google ScholarDigital Library
- 9.J. Cai, A. Condos, R. Lipton, "PSPACE is Provable by Two Provers in One Round", Structures 1991, pp. 110-115.Google Scholar
- 10.U. Feige, "On the Success Probability of the Two Provers in One Round Proof Systems", Structures 199I, pp. 116-123.Google Scholar
- 11.U. Feige, S. Goldwasser, L. Lovasz, M. Safra, M. Szegedy, "Approximating Clique is Almost NP- Complete", 32't# FOGS, I991, pp. #-12.Google Scholar
- 12.L. Fortnow, "Complexity-Theoretic Aspects of Interactive Proof Systems", Ph.D. Thesis, MIT/LCS/TR-4# 7, 1989.Google Scholar
- 13.L. Fortnow, J. Rompel, M.Sipser, "On the Power of Multi-Prover interactive Protocols", Structures 1988, pp. t56-161. Erratum in Structures 1990, pp. 318-319.Google Scholar
- 14.M. GrStschel, L. LovAsz, A. Schrijver, "Geometric Algorithms and Combinatorial Optimization", Springer- Verlag, 1988.Google Scholar
- 15.D. Lapidot, A. Shamir, "A One-Round, Two- Prover, Zero-Knowledge Protocol for NP", Crypto, 1991. Google ScholarDigital Library
- 16.D. Lapidot, A. Shamir, "Fully Parallelized Multi Prover Protocols for NEXP-time" 32'=# FOGS, 1991, pp. 13-18. Google ScholarDigital Library
- 17.L. Lov#z, "On the Shanon Capacity of a Graph", IEEE Trans. on information Theory, Vol. #5, pp. I-7, 1979.Google Scholar
- 18.L. Lov#z, A. Schrijver, "Cones of Matrices and Setfunctions, and 0-1 Optimization", 1990.Google Scholar
- 19.J. Kilian, "Strong Separation Models of Multi Prover Interactive Proofs" DIMA GS Workshop on Cryptography, October 1990.Google Scholar
- 20.D. Peleg, "On the Maximal Number of Ones in Zero-One Matrices with No Forbidden Rectangles", manuscript, 1990.Google Scholar
- 21.G. L. Peterson, J. H. Reif, "Multiple-Person Alternation", 20~' FOGS, 1979, pp. 348-363.Google Scholar
- 22.A. Shamir, "IP=PSPACE" 31st FOGS, 1990, pp. 11-15.Google Scholar
- 23.D. Sherali, W. Adams, "A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems", prcprint# 1988.Google Scholar
Index Terms
- Two-prover one-round proof systems: their power and their problems (extended abstract)
Recommendations
On the power of unique 2-prover 1-round games
STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computingA 2-prover game is called unique if the answer of one prover uniquely determines the answer of the second prover and vice versa (we implicitly assume games to be one round games). The value of a 2-prover game is the maximum acceptance probability of the ...
Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies
CCC '09: Proceedings of the 2009 24th Annual IEEE Conference on Computational ComplexityThis paper presents three results on the power of two-prover one-round interactive proof systems based on oracularization under the existence of prior entanglement between dishonest provers. It is proved that the two-prover one-round interactive proof ...
Comments