Yael Kalai: 1-round delegation for deterministic computation

Friday, October 25, 2013 - 12:45pm to 3:45pm
Pizza at 12:30pm
MSR New England (Barton room on the 1st floor of One Memorial Drive building)
Yael Kalai

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.