1-ROUND DELEGATION FOR DETERMINISTIC COMPUTATIONS*
Yael Tauman Kalai
, Microsoft Research
Date: Tuesday, October 22, 2013
Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Host: Dana Moshkovitz and Costis Daskalakis
Contact: Holly A Jones, firstname.lastname@example.org
Relevant URL: http://toc.csail.mit.edu/node/368
Speaker URL: None
TALK: 1-ROUND DELEGATION FOR DETERMINISTIC COMPUTATIONS*
We give a 1-round delegation scheme 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), where n is the input size.
The soundness of our scheme is computational, and relies on the existence of a sub-exponentially secure (computational) PIR scheme.
The proof exploits a curious connection between the problem of computation
delegation and the model of multi-prover interactive proofs that are sound
against *no-signaling* (cheating) strategies,
a model that was studied in the context of multi-prover interactive proofs with
provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light.
This is joint work with Ran Raz and Ron Rothblum.
Created by Holly A Jones at Friday, October 18, 2013 at 11:56 AM.