Arthur-Merlin streaming complexity

Tom Gur, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
Pages528-539
Number of pages12
EditionPART 1
DOIs
StatePublished - Jul 23 2013
Externally publishedYes
Event40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia
Duration: Jul 8 2013Jul 12 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7965 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other40th International Colloquium on Automata, Languages, and Programming, ICALP 2013
CountryLatvia
CityRiga
Period7/8/137/12/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Communication Complexity
  • Data Streams
  • Probabilistic Proof Systems

Fingerprint Dive into the research topics of 'Arthur-Merlin streaming complexity'. Together they form a unique fingerprint.

Cite this