Verifiable Stream Computation and Arthur-Merlin Communication
Verifiable Stream Computation and Arthur-Merlin Communication
复制标题
可验证的流计算和 Arthur-Merlin 通信
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Suresh Venkatasubramanian
中科院分区：
文献类型：
--
作者：
Amit Chakrabarti;Graham Cormode;A. Mcgregor;J. Thaler;Suresh Venkatasubramanian
在流交互校样(SIP)的设置中，客户端(验证器)需要对在线到达的海量数据流计算给定函数，但即使是一小部分数据也无法存储。它将处理外包给第三方服务(证明者)，但不愿意盲目信任该服务返回的答案。因此，该服务不能简单地提供所需的答案；它必须在看到流之后通过短暂的交互使验证者相信它的正确性。
在这项工作中，我们研究了“几乎没有互动”的饮酒。具体地说，我们证明了两轮或三轮交互足以解决几个查询问题--包括索引、中值、最近邻搜索、模式匹配和范围计数--具有多对数空间和通信成本。根据以前的工作，O(1)轮交互的效率被认为是不可能的。
另一方面，我们通过引入一种称为在线交互校样(OIP)的新层次通信模型，启动了对恒定轮次sips局限性的正式研究。这些模型的在线性质类似于在SIP中对验证者施加的流限制。我们给出了如下的上下界：(1)用其他众所周知的通信复杂性类来刻画OIP层次的每个有限层，直到二次爆破；(2)分离该层次的前四个层次；(3)揭示该层次折叠到第四个层次。我们对OIP的研究揭示了与经典的图灵机交互打样理论的显著对比和一些相似之处，建立了对现有技术开发恒定轮sip的能力的限制，并提供了(非在线)Arthur-Merlin交流的在线模型方面的新表征。
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.