Abstract
We continue the study of streaming interactive proofs (SIPs). In this setting, a client (verifier) needs to process 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 commercial cloud computing service (prover), but is unwilling to blindly trust answers returned by this service. Thus, the service must both supply the final answer and convince the verifier of its correctness.
Our primary objects of study are "barely interactive" SIPs. Specifically, we show that constant-round SIPs are surprisingly powerful, by giving polylogarithmic cost two- and three-round protocols for several "query" problems, including Index, Nearest Neighbor Search, and Range Counting. This was thought to be impossible based on previous work.
On the other hand, in order to study the limitations of constant-round SIPs, we introduce a new hierarchy of communication models that we call "online Interactive Proofs" (OIPs). We give upper and lower bounds that (1) characterize every finite level of the OIP hierarchy in terms of previously-studied communication complexity classes, and (2) separate the first four levels of the hierarchy. Our study of OIPs reveals marked contrasts and some parallels with the classic Turing Machine theory of interactive proofs.
Joint work with Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Suresh Venkatasubramanian.