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:

See other events that are part of the Theory of Computation Colloquium - 2013.

Created by Holly A Jones at Friday, October 18, 2013 at 11:56 AM.