|
 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.
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
|
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.
|
| |
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.
|
| |
3
|
L. Babai, L. Fortnow, C. Lund, "Non- Deterministic Exponential Time has Two-Prover interactive Protocols", 31st FOGS, 1990, pp. 16- 25.
|
| |
4
|
M. Beilare, P. Rogaway, "The Complexity of Continuous Optimization , manuscript.
|
 |
5
|
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]
|
| |
6
|
Boros and Hammer.
|
| |
7
|
J. CaJ, A. Condos, R.. Lipton, "On Bounded Round Multi-Prover Interactive Proof Systems", Structures 1990, pp..15-94.
|
| |
8
|
|
| |
9
|
J. Cai, A. Condos, R. Lipton, "PSPACE is Provable by Two Provers in One Round", Structures 1991, pp. 110-115.
|
| |
10
|
U. Feige, "On the Success Probability of the Two Provers in One Round Proof Systems", Structures 199I, pp. 116-123.
|
| |
11
|
U. Feige, S. Goldwasser, L. Lovasz, M. Safra, M. Szegedy, "Approximating Clique is Almost NP- Complete", 32't# FOGS, I991, pp. #-12.
|
| |
12
|
L. Fortnow, "Complexity-Theoretic Aspects of Interactive Proof Systems", Ph.D. Thesis, MIT/LCS/TR-4# 7, 1989.
|
| |
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.
|
| |
14
|
M. GrStschel, L. LovAsz, A. Schrijver, "Geometric Algorithms and Combinatorial Optimization", Springer- Verlag, 1988.
|
| |
15
|
|
| |
16
|
|
| |
17
|
L. Lov#z, "On the Shanon Capacity of a Graph", IEEE Trans. on information Theory, Vol. #5, pp. I-7, 1979.
|
| |
18
|
L. Lov#z, A. Schrijver, "Cones of Matrices and Setfunctions, and 0-1 Optimization", 1990.
|
| |
19
|
J. Kilian, "Strong Separation Models of Multi Prover Interactive Proofs" DIMA GS Workshop on Cryptography, October 1990.
|
| |
20
|
D. Peleg, "On the Maximal Number of Ones in Zero-One Matrices with No Forbidden Rectangles", manuscript, 1990.
|
| |
21
|
G. L. Peterson, J. H. Reif, "Multiple-Person Alternation", 20~' FOGS, 1979, pp. 348-363.
|
| |
22
|
A. Shamir, "IP=PSPACE" 31st FOGS, 1990, pp. 11-15.
|
| |
23
|
D. Sherali, W. Adams, "A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems", prcprint# 1988.
|
CITED BY 32
|
|
|
|
|
Alexei Kitaev , John Watrous, Parallelization, amplification, and exponential time simulation of quantum interactive proof systems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.608-617, May 21-23, 2000, Portland, Oregon, United States
|
|
|
Katalin Friedl , Zsolt Hátsági , Alexander Shen, Low-degree tests, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.57-64, January 23-25, 1994, Arlington, Virginia, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Shafi Goldwasser , Dan Gutfreund , Alexander Healy , Tali Kaufman , Guy N. Rothblum, Verifying and decoding in constant depth, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
|
|
|
|
|
|
|
|
|
Sanjeev Arora , Subhash A. Khot , Alexandra Kolla , David Steurer , Madhur Tulsiani , Nisheeth K. Vishnoi, Unique games on expanding constraint graphs are easy: extended abstract, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.1