  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 $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. 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.
