Dhiraj Holden: No Signaling Proofs with sqrt(log n) Provers in PSPACE

Abstract: 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 = sqrt(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^(-Omega(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.