About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1992
Conference paper
Two-prover one-round proof systems: Their power and their problems
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(1,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.