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

Preview

PDF WRAP_20.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (1106Kb) | Preview

Request Changes to record.

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:	Date Event 2015 Published
Date of first compliant deposit:	27 February 2016
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:	Publisher Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads