We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical streaming algorithm for a wide class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it.

As an application, we give an streaming algorithm for the Distinct Elements problem. Given a data stream of length m over alphabet of size n, the algorithm uses O(s) space and a proof of size O(w), for every sw such that swn (where O hides a polylog(mn) factor). We also prove a lower bound, showing that every streaming algorithm for the Distinct Elements problem that uses s bits of space and a proof of size w, satisfies sw=(n).As a part of the proof of the lower bound for the Distinct Elements problem, we show a new lower bound of n on the communication complexity of the Gap Hamming Distance problem, and prove its tightness