Yael Kalai: 1-round delegation for deterministic computation

In this talk we will focus on constructing multi-prover interactive proofs (MIPs) that are sound
against *no-signaling* (cheating) strategies, for any deterministic computation.
Such MIPs were studied in the context of MIPs with provers that share quantum entanglement,
and is motivated by the physical principle that information cannot travel faster than light.

Our main motivation for studying this notion is a curious connection between such MIPs and 1-round arguments (which are computationally sound).
Indeed our MIP gives a 1-round argument for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n \cdot polylog(t), and where soundness
relies on the existence of a sub-exponentially secure (computational) PIR scheme.

This is joint work with Ran Raz and Ron Rothblum.