ECCC-Report TR13-020https://eccc.weizmann.ac.il/report/2013/020Comments and Revisions published for TR13-020en-usSat, 02 Feb 2013 22:25:08 +0200
Paper TR13-020
| Arthur-Merlin Streaming Complexity |
Tom Gur,
Ran Raz
https://eccc.weizmann.ac.il/report/2013/020We 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.
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\cdot w \ge n$ (where $\tilde O$ hides a $\mathrm{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 \cdot w = \Omega(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.Sat, 02 Feb 2013 22:25:08 +0200https://eccc.weizmann.ac.il/report/2013/020