No-Signaling Proofs with O(√(log n)) Provers are in PSPACE

10/07/2019
by   Dhiraj Holden, et al.
0

No-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 2<k<poly(n) remained an open problem. We show that k-prover no-signaling proofs (with negligible soundness) for k=O(√(log n)) 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^-Ω(k^2) into a no-signaling one with value at least 2^-O(k^2). 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^-ck^2 (for some constant c>0), then the corresponding 2-prover game has value at most 1 - 2^dk^2 (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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset