![Proofs, Consensus, and Decentralizing Society_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Proofs%2C%20Consensus%2C%20and%20Decentralizing%20Society_hi-res.png.jpg?itok=gluZ2qCs)
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.