TY - GEN

T1 - Arthur-Merlin streaming complexity

AU - Gur, Tom

AU - Raz, Ran

PY - 2013/7/23

Y1 - 2013/7/23

N2 - We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical 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 AM streaming algorithm for the Distinct Elements problem. Given a data stream of length m over alphabet of size n, the algorithm uses Õ(s) space and a proof of size Õ(w), for every s,w such that s·w ≥ n (where Õ hides a polylog(m,n) factor). We also prove a lower bound, showing that every MA streaming algorithm for the Distinct Elements problem that uses s bits of space and a proof of size w, satisfies s·w = Ω(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 MA communication complexity of the Gap Hamming Distance problem, and prove its tightness.

AB - We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical 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 AM streaming algorithm for the Distinct Elements problem. Given a data stream of length m over alphabet of size n, the algorithm uses Õ(s) space and a proof of size Õ(w), for every s,w such that s·w ≥ n (where Õ hides a polylog(m,n) factor). We also prove a lower bound, showing that every MA streaming algorithm for the Distinct Elements problem that uses s bits of space and a proof of size w, satisfies s·w = Ω(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 MA communication complexity of the Gap Hamming Distance problem, and prove its tightness.

KW - Communication Complexity

KW - Data Streams

KW - Probabilistic Proof Systems

UR - http://www.scopus.com/inward/record.url?scp=84880322778&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880322778&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39206-1_45

DO - 10.1007/978-3-642-39206-1_45

M3 - Conference contribution

AN - SCOPUS:84880322778

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 528

EP - 539

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -