- 1-ROUND DELEGATION FOR DETE...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in October 2013
1-ROUND DELEGATION FOR DETERMINISTIC COMPUTATIONS*
Speaker:
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
Public: Yes
Location: 32-G449
Event Type:
Room Description:
Host: Dana Moshkovitz and Costis Daskalakis
Contact: Holly A Jones, hjones01@csail.mit.edu
Relevant URL: http://toc.csail.mit.edu/node/368
Speaker URL: None
Speaker Photo:
None
Reminders to:
toc@csail.mit.edu
Reminder Subject:
TALK: 1-ROUND DELEGATION FOR DETERMINISTIC COMPUTATIONS*
Abstract:
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.
Research Areas:
Impact Areas:
Created by Holly A Jones at Friday, October 18, 2013 at 11:56 AM.