  Motivated by the trend to outsource work to commercial cloud computing
services, we consider a variation of the streaming paradigm where a streaming
algorithm can be assisted by a powerful helper that can provide annotations to
the data stream. We extend previous work on such {\em annotation models} by
considering a number of graph streaming problems. Without annotations,
streaming algorithms for graph problems generally require significant memory;
we show that for many standard problems, including all graph problems that can
be expressed with totally unimodular integer programming formulations, only a
constant number of hash values are needed for single-pass algorithms given
linear-sized annotations. We also obtain a protocol achieving \textit{optimal}
tradeoffs between annotation length and memory usage for matrix-vector
multiplication; this result contributes to a trend of recent research on
numerical linear algebra in streaming models.
