Friday, December 6, 2019 - 10:30am to 12:00pm
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 = √(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.