The Library
Verifiable stream computation and Arthur-Merlin communication
Tools
Tools
Tools
Chakrabarti, Amit, Cormode, Graham, McGregor, Andrew, Thaler, Justin and Venkatasubramanian, Suresh (2015) Verifiable stream computation and Arthur-Merlin communication. In: 30th Conference on Computational Complexity (CCC’15), Portland, Oregon, 17-19 Jun 2015. Published in: Leibniz international proceedings in informatics (LIPIcs) pp. 217-243. ISSN 1868-8969. doi:10.4230/LIPIcs.CCC.2015.217
|
PDF
WRAP_20.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (1106Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.217
Abstract
In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling to blindly trust answers returned by this service. Thus, the service cannot simply supply the desired answer; it must convince the verifier of its correctness via a short interaction after the stream has been seen.
In this work we study “barely interactive” SIPs. Specifically, we show that two or three rounds of interaction suffice to solve several query problems-including Index, Median, Nearest Neighbor Search, Pattern Matching, and Range Counting-with polylogarithmic space and communication costs. Such efficiency with O(1) rounds of interaction was thought to be impossible based on previous work.
On the other hand, we initiate a formal study of the limitations of constant-round SIPs by introducing a new hierarchy of communication models called Online Interactive Proofs (OIPs). The online nature of these models is analogous to the streaming restriction placed upon the verifier in an SIP. We give upper and lower bounds that (1) characterize, up to quadratic blowups, every finite level of the OIP hierarchy in terms of other well-known communication complexity classes, (2) separate the first four levels of the hierarchy, and (3) reveal that the hierarchy collapses to the fourth level. Our study of OIPs reveals marked contrasts and some parallels with the classic Turing Machine theory of interactive proofs, establishes limits on the power of existing techniques for developing constant-round SIPs, and provides a new characterization of (non-online) Arthur-Merlin communication in terms of an online model.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Cloud computing, Streaming technology (Telecommunications) | ||||
| Journal or Publication Title: | Leibniz international proceedings in informatics (LIPIcs) | ||||
| Publisher: | Schloss Dagstuhl ; Leibniz-Zentrum fuer Informatik | ||||
| ISSN: | 1868-8969 | ||||
| Official Date: | 2015 | ||||
| Dates: |
|
||||
| Page Range: | pp. 217-243 | ||||
| DOI: | 10.4230/LIPIcs.CCC.2015.217 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Open Access | ||||
| Funder: | National Science Foundation (U.S.) (NSF), Yahoo! Research Labs, European Commission (EC), Royal Society (Great Britain). Wolfson Research Merit Award (RSWRMA), Simons Institute for the Theory of Computing | ||||
| Grant number: | CCF-1217375 (NSF), ERC-2014-CoG-647557 (EC), IIS-1251110 (NSF) | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 30th Conference on Computational Complexity (CCC’15) | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Portland, Oregon | ||||
| Date(s) of Event: | 17-19 Jun 2015 | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
