Non-signaling proofs, motivated by quantum computation, have found applications in cryptography and hardness of approximation. An important open problem is characterizing the power of no-signaling proofs. It is known that 2-prover no-signaling proofs are characterized by PSPACE, and that no-signaling proofs with
poly(n)-provers are characterized by EXP. However, the power of
k-prover no-signaling proofs, for
20), then the corresponding 2-prover game has value at most
1−2dk2 (for some constant~
d>0). In the second route we show that the value of a sub-no-signaling game can be approximated in space that is polynomial in the communication complexity and exponential in the number of provers.
Non-signaling proofs, motivated by quantum computation, have found applications in cryptography and hardness of approximation. An important open problem is characterizing the power of no-signaling proofs. It is known that 2-prover no-signaling proofs are characterized by PSPACE, and that no-signaling proofs with poly(n)-provers are characterized by EXP. However, the power of k-prover no-signaling proofs, for 2kpoly(n) remained an open problem. We show that k-prover no-signaling proofs (with negligible soundness) for k=O(√logn) are contained in PSPACE. We prove this via two different routes that are of independent interest. In both routes we consider a relaxation of no-signaling called sub-no-signaling. Our main technical contribution (which is used in both our proofs) is a reduction showing how to convert any sub-no-signaling strategy with value at least 1−2−Ω(k2) into a no-signaling one with value at least 2−O(k2). In the first route, we show that the classical prover reduction method for converting k-prover games into 2-prover games carries over to the no-signaling setting with the following loss in soundness: if a k-player game has value less than 2−ck2 (for some constant~c>0), then the corresponding 2-prover game has value at most 1−2dk2 (for some constant~d>0). In the second route we show that the value of a sub-no-signaling game can be approximated in space that is polynomial in the communication complexity and exponential in the number of provers.
This 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 system for PSPACE by Cai, Condon, and Lipton [JCSS 48:183-193, 1994] still achieves exponentially small soundness error in the existence of prior entanglement between dishonest provers (and more strongly, even if dishonest provers are allowed to use arbitrary no-signaling strategies). It follows that, unless the polynomial-time hierarchy collapses to the second level, two-prover systems are still advantageous to single-prover systems even when only malicious provers can use quantum information. It is also shown that a "dummy" question may be helpful when constructing an entanglement-resistant multi-prover system via oracularization. This affirmatively settles a question posed by Kempe et al. [FOCS 2008, pp. 447-456] and every language in NEXP is proved to have a two-prover one-round interactive proof system even against entangled provers, albeit with exponentially small gap between completeness and soundness. In other words, it is NP-hard to approximate within an inverse-polynomial the value of a classical two-prover one-round game against entangled provers. Finally, both for the above proof system for NEXP and for the quantum two-prover one-round proof system for NEXP proposed by Kempe et al., it is proved that exponentially small completeness-soundness gaps are best achievable unless soundness analysis uses the structure of the underlying system with unentangled provers.