TY - GEN
T1 - Arthur-Merlin streaming complexity
AU - Gur, Tom
AU - Raz, Ran
PY - 2013
Y1 - 2013
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 -