论文标题
图形问题的流验证：最佳权衡和非线性草图
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches
论文作者
论文摘要
我们在增强的数据流设置中研究了图表计算，其中一个由空间的客户端读取大量图的边缘可能会将其某些工作委托给云服务。我们寻求算法，允许客户端验证云服务发送的声称的证明，即云中完成的工作是正确的。从Chakrabarti等人开始的工作线。 （ICALP 2009）为几种统计和图理论问题提供了这样的算法，我们称之为方案，其中许多问题在证明的长度与流验验证者使用的空间之间表现出了折衷。 这项工作为许多基本的图形问题设计了新方案 - 包括三角计数，最大匹配，拓扑排序和最短的路径 - 过去的工作要么未能在这两个关键的复杂性措施之间获得平稳的权衡，要么仅获得了次优的折衷方案。我们的关键创新是具有验证者计算输入流的某些非线性草图，从而导致新的或改进的权衡。在许多情况下，我们的计划实际上为对数因素提供了最佳的权衡。 具体来说，对于我们研究的大多数图形问题，众所周知，验证者的空间成本$ v $和证明长度$ h $的产品必须至少为$ω（n^2）$，对于$ n $ vertex图形。但是，匹配的上限仅以$ h $和$ v $的少数设置而闻名。例如，为了计数三角形和最大匹配，本曲线上的成本的方案仅以$（h = \ tilde {o}（n^2）而闻名$（h = \ tilde {o}（1），v = \ tilde {o}（n^2））$。这项工作的一个主要信息是，通过利用非线性草图，可以实现权衡曲线上的重要``部分''成本。
We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that the work done in the cloud is correct. A line of work starting with Chakrabarti et al. (ICALP 2009) has provided such algorithms, which we call schemes, for several statistical and graph-theoretic problems, many of which exhibit a tradeoff between the length of the proof and the space used by the streaming verifier. This work designs new schemes for a number of basic graph problems---including triangle counting, maximum matching, topological sorting, and single-source shortest paths---where past work had either failed to obtain smooth tradeoffs between these two key complexity measures or only obtained suboptimal tradeoffs. Our key innovation is having the verifier compute certain nonlinear sketches of the input stream, leading to either new or improved tradeoffs. In many cases, our schemes in fact provide optimal tradeoffs up to logarithmic factors. Specifically, for most graph problems that we study, it is known that the product of the verifier's space cost $v$ and the proof length $h$ must be at least $Ω(n^2)$ for $n$-vertex graphs. However, matching upper bounds are only known for a handful of settings of $h$ and $v$ on the curve $h \cdot v=\tildeΘ(n^2)$. For example, for counting triangles and maximum matching, schemes with costs lying on this curve are only known for $(h=\tilde{O}(n^2), v=\tilde{O}(1))$, $(h=\tilde{O}(n), v=\tilde{O}(n))$, and the trivial $(h=\tilde{O}(1), v=\tilde{O}(n^2))$. A major message of this work is that by exploiting nonlinear sketches, a significant ``portion'' of costs on the tradeoff curve $h \cdot v = n^2$ can be achieved.
