Two Player Hidden Pointer Chasing and Multi-Pass Lower Bounds in Turnstile Streams

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{H}\mathsf{P}\mathsf{C}}^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{H}\mathsf{P}\mathsf{C}}^2$) of ${\mathsf{H}\mathsf{P}\mathsf{C}}^4$ that has matching communication complexity to ${\mathsf{H}\mathsf{P}\mathsf{C}}^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{H}\mathsf{P}\mathsf{C}}^2$, we retain the streaming and query complexity lower bounds by (Assadi, Chen, and Khanna, 2019). Further, by giving reductions from ${\mathsf{H}\mathsf{P}\mathsf{C}}^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 $\omega (\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^{\mathrm{\Omega }(1)}$ passes over the turnstile stream. Our reductions can be modified to use ${\mathsf{H}\mathsf{P}\mathsf{C}}^4$ as well.