Speaker: Graham Cormode

Graham Cormode, AT&T Labs-Research talks about "Streaming Graph Computations with a Helpful Advisor".

• Date: November 12, 2010
• Time: 1:00 pm
• Location: CSIC 3117

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 necessary 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 number of graph stream problems. Without annotations, streaming algorithms for graph problems generally require significant memory