Time-Optimal Interactive Proofs for Circuit Evaluation
Speaker: Justin Thaler, Harvard University
Date: Wednesday, March 13 2013
Time: 4:00PM to 5:00PM
Refreshments: 4:00PM
Location: G575
Host: Raluca Ada Popa, MIT
Contact: Raluca Ada Popa, raluca@csail.mit.edu
Abstract: A potential problem in outsourcing work to commercial cloud computing services is trust. If we store a large data set with a service provider, and ask them to perform a computation on that data set -- for example, to compute the shortest path between two vertices in a large graph -- how can we know the computation was performed correctly? Obviously we don't want to compute the result ourselves, and we might not even be able to store all the data locally.
Surprisingly powerful protocols for verifying outsourced computations were discovered within the computer science theory community several decades ago, in the form of interactive proofs and their brethren. However, until recently these protocols were considered theoretical curiosities, far too inefficient for actual deployment. In this talk, I will describe research efforts that have sought to overturn this point of view. These efforts have revisited some of the most powerful protocols in the theory literature and drastically improved their efficiency. We complement the theory with implementations demonstrating that practical general-purpose interactive proofs may be right around the corner.
Bio: Justin Thaler is currently finishing his PhD at Harvard University. His research focuses on algorithms for massive data sets, verifiable computation, and computational learning theory.
See other events that are part of CSAIL Security Seminar 2012/2013
See other events happening in March 2013
