Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

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:
DateEvent
2015Published
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us