论文标题
多通绘图流式流式的下限，用于周期计数，最大切割，匹配大小和其他问题
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
论文作者
论文摘要
考虑流模型中的以下差距周期计数问题：$ 2 $的$ n $ n $ n $ vertex图$ g $的边缘在流中一一到达，我们保证$ g $是$ k $ chyccycles或$ 2k $ $ $ $ $ k $的$ k $ boter;目的是区分这两种情况。 Verbin和Yu [Soda 2011]引入了此问题，并表明任何单个通信流算法求解它都需要$ n^{1-Ω（\ frac {1} {1} {k} {k}）} $ space。此结果及其背后的技术 - 布尔隐藏的超匹配通信问题 - 此后已广泛用于证明各种问题流的下限。 尽管具有重要性和广泛的应用范围，但动词和YU的下边界技术具有关键的弱点，这是所有随后的结果所遗传的：只有只有在两轮沟通中可以解决一轮沟通并在两轮比赛中进行对数沟通，就很难进行布劳隐藏的超匹配问题。因此，从该问题得出的所有流界仅适用于单通算法。 我们证明了第一个用于间隙周期计数问题的多通量下限：任何$ p $ - 可以区分$ k $ -cycles vs $ 2k $ -cycles的分离算法 - 甚至$ k $ -cycles-甚至一个hamiltonian vs hamiltonian vs一个汉密尔顿周期 - 需要$ n^{1- \ frac {1- \ frac} $ plac} $ plac} $ {1} $ { 空间。作为结果的必然，我们可以将许多先前的下限扩展到多通算法。例如，我们现在可以证明任何流算法都$（1+ε）$ - 近似于最大切割的值，最大匹配大小或等级为$ n $ - by- $ n $矩阵，都需要$ n^{ω（1）$ n^{ω（1）$ space或$ω（\ log或log log {\ freac {\ freac {\ freac {\ freac {1}} $ vaste} $对于所有这些问题，先前的工作就打开了甚至只有两次通过的$ O（\ log {n}）$ space算法的可能性。
Consider the following gap cycle counting problem in the streaming model: The edges of a $2$-regular $n$-vertex graph $G$ are arriving one-by-one in a stream and we are promised that $G$ is a disjoint union of either $k$-cycles or $2k$-cycles for some small $k$; the goal is to distinguish between these two cases. Verbin and Yu [SODA 2011] introduced this problem and showed that any single-pass streaming algorithm solving it requires $n^{1-Ω(\frac{1}{k})}$ space. This result and the technique behind it -- the Boolean Hidden Hypermatching communication problem -- has since been used extensively for proving streaming lower bounds for various problems. Despite its significance and broad range of applications, the lower bound technique of Verbin and Yu comes with a key weakness that is inherited by all subsequent results: the Boolean Hidden Hypermatching problem is hard only if there is exactly one round of communication and can be solved with logarithmic communication in two rounds. Therefore, all streaming lower bounds derived from this problem only hold for single-pass algorithms. We prove the first multi-pass lower bound for the gap cycle counting problem: Any $p$-pass streaming algorithm that can distinguish between disjoint union of $k$-cycles vs $2k$-cycles -- or even $k$-cycles vs one Hamiltonian cycle -- requires $n^{1-\frac{1}{k^{Ω(1/p)}}}$ space. As a corollary of this result, we can extend many of previous lower bounds to multi-pass algorithms. For instance, we can now prove that any streaming algorithm that $(1+ε)$-approximates the value of MAX-CUT, maximum matching size, or rank of an $n$-by-$n$ matrix, requires either $n^{Ω(1)}$ space or $Ω(\log{(\frac{1}ε)})$ passes. For all these problems, prior work left open the possibility of even an $O(\log{n})$ space algorithm in only two passes.
