### Interdisciplinary Seminar Series

Title: SIPping from the firehose: Streaming Interactive Proofs for verifying computations

Speaker: **Graham Cormode**, AT&T Labs

Date: Monday, May 17, 2010 12:00 - 1:00 pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

When handling large quantities of data, it is desirable to outsource the
computational effort to a third party: this captures current efforts in
cloud computing, but also scenarios within trusted computing systems and
inter-organizational data sharing. When the third party is not fully
trusted, it is desirable to give assurance that the computation has been
perfomed correctly. This talk presents some recent results in designing
new protocols for verifying computations which are streaming in nature:
the verifier (data owner) needs only a single pass over the input, storing
a sublinear amount of information, and follows a simple protocol with a
prover (serice provider) that takes a small number of rounds. A dishonest
prover fools the verifier with only polynomially small probabiliy, while
an honest prover's answer is always accepted. Within this model, we show
protocols for a variety of problems that select items from the input (e.g.
median, heavy hitters), or compute certain aggregates or structures (e.g.
frequency moments, number of triangles in a graph). These problems
require linear space to compute (exactly) in the traditional streaming
model, showing that outsourcing can exponentially reduce the effort needed
by the verifier to obtain correct answers