Abstract
No-signaling proofs, originally motivated by quantum computations, 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(\sqrt{log n}) are contained in PSPACE.
This is joint work with Dhiraj Holden.