期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2019
卷号：2019
页码：1-19
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give new algorithms in the annotated data streaming setting---also known as verifiable data stream computation---for certain graph problems. This setting is meant to model outsourced computation, where a space-bounded verifier limited to sequential data access seeks to overcome its computational limitations by engaging a powerful prover, without needing to trust the prover. As is well established, several problems that admit no sublinear-space algorithms under traditional streaming do allow protocols using a sublinear amount of prover/verifier communication and sublinear-space verification. We give algorithms for many well-studied graph problems including triangle counting, its generalization to subgraph counting, maximum matching, problems about the existence (or not) of short paths, finding the shortest path between two vertices, and testing for an independent set. While some of these problems have been studied before, our results achieve new tradeoffs between space and communication costs that were hitherto unknown. In particular, two of our results disprove explicit conjectures of Thaler (ICALP, 2016) by giving triangle counting and maximum matching algorithms for n -vertex graphs, using o ( n ) space and o ( n 2 ) communication.
关键词：Arthur;Merlin ; communication complexity ; maximum matching ; streaming interactive proofs ; Triangle counting
