We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical ${\mathcal{AM}}$ 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.#R##N##R##N#As an application, we give an ${\mathcal{AM}}$ streaming algorithm for the Distinct Elements problem. Given a data stream of length m over alphabet of size n, the algorithm uses $\tilde O(s)$ space and a proof of size $\tilde O(w)$, for every s,w such that s ·w≥n (where $\tilde O$ hides a polylog(m,n) factor). We also prove a lower bound, showing that every ${\mathcal{MA}}$ streaming algorithm for the Distinct Elements problem that uses s bits of space and a proof of size w, satisfies s ·w=Ω(n).#R##N##R##N#As a part of the proof of the lower bound for the Distinct Elements problem, we show a new lower bound of $\Omega \left( \sqrt n \right )$ on the ${\mathcal{MA}}$ communication complexity of the Gap Hamming Distance problem, and prove its tightness.
['Tom Gur', 'Ran Raz']
Arthur-Merlin streaming complexity