Practical Verified Computation with Streaming Interactive Proofs: Justin Thaler, Harvard

Starts:
10:00 am on Monday, November 5, 2012
Ends:
12:00 pm on Monday, November 5, 2012
Location:
MCS 137
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 eigenvalues of a large graph, or to compute a linear program on a large matrix derived from a database -- 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. This leads to new problems in the streaming paradigm: we consider a streaming algorithm (modeling a user with limited memory and computational resources) that can be assisted by a powerful helper (the service provider). The goal of the service provider is to not only provide the user with answer, but to convince the user the answer is correct. In this talk, I will describe a recent line of work exploring the application of proof systems to problems that are streaming in nature. The protocols I will discuss utilize and extend powerful ideas from communication complexity and the theory of interactive proofs, and I will argue that many are highly practical, achieving millions of updates per second and requiring little space and communication. Joint work with Amit Chakrabarti, Graham Cormode, Andrew McGregor, Michael Mitzenmacher, and Ke Yi