No-signaling is an intriguing notion motivated by quantum mechanics. In this talk I will explain the related notion of no-signaling multi-prover interactive proofs (MIPs), and will show interesting applications  to cryptography and hardness of approximation.  Specifically, first we will see how such proofs can be used to obtain succinct and efficiently verifiable (single prover) proofs for the correctness of any (deterministic) computation [K-Raz-Rothblum STOC 20014].  Then we will see  how it can be used to prove that the value of a linear program cannot be approximated by a small space algorithm [K-Raz-Regev2017].  Finally, we will discuss the power of such proof systems. 

It is known that no-signaling MIPs with poly(n) provers are characterized by EXP  [K-Raz-Rothblum STOC 20014], and no-signaling MIPs with 2 provers are characterized by PSPACE. Until recently, 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.