Title: Practical Verified Computation with Streaming Interactive Proofs

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 give a unified overview of a recent line of work
exploring the application of proof systems to problems that are
streaming in nature. In all of these protocols, an honest service
provider can always convince the data owner that the answer is
correct, while a dishonest prover will be caught with high
probability. 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