论文标题
两个播放器隐藏的指针追逐和旋转栅流中的多通道下限
Two Player Hidden Pointer Chasing and Multi-Pass Lower Bounds in Turnstile Streams
论文作者
论文摘要
由于引理3.4证明的错误，作者撤回了本文。 ------------------------------------------------------------------------------------------------------------------------------------------------------ 由于引理3.4z（Assadi，Chen和Khanna，2019年）的错误证明，作者已撤回了本文，定义了一个4播放器的隐藏式调音（$ \ Mathsf {hpc}^4 $），并且使用它，在计算中的图形上有强大的多量范围，以使较低的多峰值范围的绘制范围和较低的计算模型。我们提出了$ \ mathsf {hpc}^4 $的两种玩家版本（$ \ mathsf {hpc}^2 $），其具有匹配的通信复杂性与$ \ Mathsf {hpc}^4 $。我们的公式使我们能够通过简单的直接和参数来降低其通信复杂性。使用$ \ mathsf {hpc}^2 $的通信复杂性的下限，我们保留了（Assadi，Chen和Khanna，2019年）的流和查询复杂性下限。 此外，通过从$ \ mathsf {hpc}^2 $提供减少，我们证明了在旋转栅流中的图形问题的新的多通路空间下限。特别是，我们表明，任何计算$ n $ - vertex图中最大加权匹配的确切权重的算法都需要$ \ tilde {o}（n^{2}）$空间需要$ n^{2-o（1）} $ space，除非它使$ n^{ω（1）} $通过旋转栅流。可以修改我们的降低以使用$ \ Mathsf {HPC}^4 $。
The authors have withdrawn this paper due to an error in the proof of Lemma 3.4. -------------------------------------------------------------------------------------------- The authors have withdrawn this paper due to an error in the proof of Lemma 3.4z(Assadi, Chen, and Khanna, 2019) define a 4-player hidden-pointer-chasing ($\mathsf{HPC}^4$), and using it, give strong multi-pass lower bounds for graph problems in the streaming model of computation and a lower bound on the query complexity of sub-modular minimization. We present a two-player version ($\mathsf{HPC}^2$) of $\mathsf{HPC}^4$ that has matching communication complexity to $\mathsf{HPC}^4$. Our formulation allows us to lower bound its communication complexity with a simple direct-sum argument. Using this lower bound on the communication complexity of $\mathsf{HPC}^2$, we retain the streaming and query complexity lower bounds by (Assadi, Chen, and Khanna, 2019). Further, by giving reductions from $\mathsf{HPC}^2$, we prove new multi-pass space lower bounds for graph problems in turnstile streams. In particular, we show that any algorithm which computes the exact weight of the maximum weighted matching in an $n$-vertex graph requires $\tilde{O}(n^{2})$ space unless it makes $ω(\log n)$ passes over the turnstile stream, and that any algorithm which computes the minimum $s\text{-}t$ distance in an $n$-vertex graph requires $n^{2-o(1)}$ space unless it makes $n^{Ω(1)}$ passes over the turnstile stream. Our reductions can be modified to use $\mathsf{HPC}^4$ as well.
