Verifiable Stream Computation and Arthur-Merlin Communication

The simplest setting of two-party communication is the one-way model, where Alice, who holds an input x, must send Bob, who holds y, a single randomized message enabling him to estimate some function f(x,y). The main complexity measure of interest is the length of the message Alice must send. We study the Arthur-Merlin extension of this model, wherein the mortal players (Alice and Bob) may seek the advice of the powerful wizard Merlin, who knows both x and y, but might not be truthful. Despite this uncertainty about Merlin's intentions, one can design protocols for certain problems that achieve considerably lower communication---sometimes exponentially lower---than is possible in the classic model.

I shall describe some protocols in this Arthur-Merlin setting and the relation of (several) Arthur-Merlin communication models to the classic model. I shall also discuss the connection between Arthur-Merlin protocols and verifiable data streaming computation.

(Based on the upcoming CCC 2015 paper with the same title, joint with Cormode, McGregor, Thaler, and Venkatasubramanian.)