  When delegating computation to a service provider, as in cloud computing, we
seek some reassurance that the output is correct and complete. Yet recomputing
the output as a check is inefficient and expensive, and it may not even be
feasible to store all the data locally. We are therefore interested in proof
systems which allow a service provider to prove the correctness of its output
to a streaming (sublinear space) user, who cannot store the full input or
perform the full computation herself.
  Our approach is two-fold. First, we describe a carefully chosen instantiation
of one of the most efficient general-purpose constructions for arbitrary
computations (streaming or otherwise), due to Goldwasser, Kalai, and Rothblum.
This requires several new insights to make the methodology more practical. Our
main contribution is in achieving a prover who runs in time O(S(n) log S(n)),
where S(n) is the size of an arithmetic circuit computing the function of
interest. Our experimental results demonstrate that a practical general-purpose
protocol for verifiable computation may be significantly closer to reality than
previously realized.
  Second, we describe techniques that achieve genuine scalability for protocols
fine-tuned for specific important problems in streaming and database
processing. Focusing in particular on non-interactive protocols for problems
ranging from matrix-vector multiplication to bipartite perfect matching, we
build on prior work to achieve a prover who runs in nearly linear-time, while
obtaining optimal tradeoffs between communication cost and the user's working
memory. Existing techniques required (substantially) superlinear time for the
prover. We argue that even if general-purpose methods improve, fine-tuned
protocols will remain valuable in real-world settings for key problems, and
hence special attention to specific problems is warranted.
