Non-signaling proofs with o(√ log n) provers are in PSPACE

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 non-signaling proofs. It is known that non-signaling proofs with two provers are characterized by PSPACE and that non-signaling proofs with poly(n)-provers are characterized by EXP. However, the power of k-prover non-signaling proofs, for 2 < k < poly(n) remained an open problem.

We show that k-prover non-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 non-signaling called sub-non-signaling. Our main technical contribution (which is used in both our proofs) is a reduction showing how to convert any sub-non-signaling strategy with value at least 1 -2 -Ω(k 2 ) into a non-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 non-signaling setting with the following loss in soundness: if a k-prover game has value less than 2 -ck 2 (for some constant c > 0), then the corresponding 2-prover game has value less than 1 -2 dk 2 (for some constant d > 0). In the second route we show that the value of a sub-non-signaling game can be approximated in space that is polynomial in the communication complexity and exponential in the number of provers.