Fall 2019

No-Signaling Proofs with O(\sqrt{log n})-Provers is in PSPACE

Tuesday, Sep. 24, 2019 9:30 am10:30 am PDT

Add to Calendar


Yael Kalai (Microsoft Research)

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.