Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing

Radhakrishnan, Jaikumar; Reddy, Chaitanya; Venkat, Rakesh

doi:10.4230/LIPIcs.ITCS.2026.110

Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing

Jaikumar Radhakrishnan

ICTS-TIFR, Bengaluru, India Chaitanya Reddy

Department of Computer Science and Engineering, IIT Hyderabad, India Rakesh Venkat

Department of Computer Science and Engineering, IIT Hyderabad, India

Abstract

We consider the communication complexity of the graph connectivity problem, where the edges of an $n$ -vertex undirected graph $G$ are distributed between two parties Alice and Bob, who are then required to communicate to determine if $G$ is connected. We show that in any randomized protocol with two-rounds of communication, Alice and Bob must exchange $\Omega(n\log n)$ bits; such a lower bound for one-round protocols was shown by Sun and Woodruff (APPROX/RANDOM 2015). A one-round deterministic protocol, where Alice sends $O(n\log n)$ bits and Bob determines the answer, was observed by Hajnal, Maass and Turan (STOC 1988); they also showed a matching lower bound of $\Omega(n\log n)$ bits for deterministic protocols with unbounded rounds of communication. For randomized protocols, a reduction from the set disjointness problem due to Babai, Frankl and Simon (FOCS 1986) implies a randomized lower bound of $\Omega(n)$ even with unbounded rounds of communication. Whether this lower bound can be improved to $\Omega(n\log n)$ has been an outstanding open question, whose algorithmic implications were recently emphasized by Apers, Efron, Gawrychowski, Lee, Mukopadhyay and Nanongkai (FOCS 2022). Our lower bound for randomized two-round protocols is based on a reduction from a restricted version of the two-player pointer chasing problem originally studied by Papadimitriou and Sipser (JCSS 1984). Using this reduction, we show an $\omega(n)$ lower bounds on graph connectivity for any constant number of rounds by extending deterministic lower bounds shown by Ponzio, Radhakrishnan and Venkatesh (JCSS 2001) to the randomized setting.

Keywords and phrases:

Communication complexity

Funding:

Jaikumar Radhakrishnan: Department of Atomic Energy, Government of India, under project number RTI4001.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Communication complexity

DOI:

10.4230/LIPIcs.ITCS.2026.110

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Graph problems have been extensively studied in various computational settings – algorithms, decision trees, streaming algorithms, distributed algorithms and communication protocols. In this paper, we focus on the two-party communication setting: the edges of the $n$ -vertex undirected graph $G=(V,E)$ are distributed between two parties Alice and Bob (some of the edges may be given to both), who then need to exchange messages in order to compute some function of $G$ ; the goal is to minimize the number of bits exchanged. Early works [4, 7] investigated properties such as connectivity, st-connectivity, bipartiteness, proving both lower and upper bounds on the amount of communication needed in this model. Other properties such as triangle-freeness, existence of Eulerian tours, $k$ -edge connectivity, and cycle freeness among others have been studied and new lower bounds have been obtained in subsequent works [8, 19]. More recently, graph problems have been extensively studied for trade-offs between space requirements and the number of passes for streaming algorithms for estimating quantities like matchings, cuts, etc., in various settings (see [2] and the references therein). Lower bounds in these settings are also typically shown by considering the communication complexity of some associated graph problem.

A fundamental problem in this domain is the connectivity problem $\mathsf{Conn}_{n}$ : Alice and Bob need to determine if $G$ is connected. The randomized complexity of this problem was studied by Babai, Frankl and Simon [4], who showed a reduction from the set disjointness problem; when combined with the $\Omega(n)$ lower bound for the set disjointness problem [18, 9], this implies an $\Omega(n)$ lower bound for the randomized communication complexity of $\mathsf{Conn}_{n}$ . There exists an $O(n\log n)$ -bit $1$ -round deterministic communication protocol: Alice sends a spanning forest of her edges to Bob, who then determines the answer. Hajnal, Maas and Turan [7] showed a deterministic lower bound of $\Omega(n\log n)$ for connectivity¹¹1In fact, they show that the bound holds in a stronger arbitrary partitioning model of the edges.. For randomized protocols with an unbounded number of rounds of communication, closing this gap between the upper and lower bounds has remained a major open question since the work of [4], and has been mentioned [1, 8] as one of the outstanding open questions in communication complexity. An optimal lower bound on $\mathsf{Conn}_{n}$ also implies the optimality of some query algorithms [1]. A randomized lower bound of $\Omega(n\log n)$ was shown for one-round protocols by [19]; however, no lower bound better than $\Omega(n)$ was known for randomized protocols with more than one round of communication²²2Following convention, we only require one of the players to know the answer for $\mathsf{Conn}_{n}$ at the end of the protocol..

We show an optimal randomized lower bound of $\Omega(n\log n)$ on $\mathsf{Conn}_{n}$ against protocols with two rounds of communication, by relating it to the pointer chasing problem introduced by Papdimitrou and Sipser [14] to study tradeoffs between the number of rounds of communication, and number of bits communicated. In the two-party pointer chasing problem³³3Our definition differs from the standard definition, for we insist that the pointers given to Alice and Bob correspond to bijections – our reduction will make crucial use of this property. Note, however, that our lower bounds with this restriction on the inputs imply similar lower bounds for the problem without any restriction., the edges of a directed bipartite graph $G=(\mathcal{V}_{A}\uplus\mathcal{V}_{B},E)$ (where $|\mathcal{V}_{A}|,|\mathcal{V}_{B}|=n$ ) are distributed between Alice and Bob in the following way: Alice receives a one-to-one function $f_{A}:\mathcal{V}_{A}\rightarrow\mathcal{V}_{B}$ and Bob receives a one-to-one function $f_{B}:\mathcal{V}_{B}\rightarrow\mathcal{V}_{A}$ , which we view as (directed) matchings $E_{A}$ and $E_{B}$ respectively. A fixed starting vertex $v_{0}\in\mathcal{V}_{A}$ and a parameter $k$ are known to both players. We consider two versions of the problem: the full-version and the bit-version. In the full-version of the problem, $\textsf{PC}(n,k)$ , the goal is to find the identity of the unique vertex $v_{k}$ found by following the $k$ -length path $v_{0}\rightarrow v_{1}:=f_{A}(v_{0})\rightarrow v_{2}:=f_{B}(v_{1})\rightarrow% \ldots\rightarrow v_{k}:=f(v_{k-1})$ , where $f=f_{A}$ , if $k$ is odd, and $f=f_{B}$ , if $k$ is even. In the bit-version of the problem, $\textsf{bPC}(n,k)$ , Alice and Bob need to determine just the last bit or the parity of $v_{k}$ . At the end, both players must know the answer.⁴⁴4The extra round that is needed for both players to know the answer in pointer chasing is often crucial.

There is a simple deterministic $k$ -round protocol that exchanges $O(k\log n)$ bits to find $v_{k}$ , where Alice starts by sending $v_{1}$ , and in the $i$ -th round the appropriate player sends $v_{i}$ since they already know $v_{i-1}$ . A major focus of previous work has been to show a separation between the amount of communication needed in the above case versus if only $k-1$ rounds of communication are allowed, or $k$ rounds are allowed but Bob (the wrong player, since he does not know $f_{A}$ ) starts the communication. With this restriction, for a general $k$ , a sequence of works [13, 20, 11] have resulted in a $\Omega(n/k)$ lower bound against randomized protocols. For constant $k$ , Ponzio, Radhakrishnan and Venkatesh [15] show a $\Omega(n\log^{(k-1)}n)$ lower bound for the full version. As for upper bounds, Nisan and Wigderson [13] gave a randomized protocol with communication $O((k+n/k)\log n)$ , and Damm, Jukna and Sgall [5] design a deterministic protocol with communication $O(n\log^{(k-1)}n)$ , for constant $k$ .

Our reduction from to $\mathsf{Conn}_{n}$ in fact passes through another related problem. In the Hamiltonian cycle problem, $\mathsf{HamCycle}(n)$ , the inputs to Alice and Bob are the same as in $\textsf{PC}(n,k)$ , that is, matchings represented as one-to-one functions $f_{A}$ and $f_{B}$ . Alice and Bob need to determine if the union of $f_{A}$ and $f_{B}$ is a Hamiltonian Cycle, or it consists of more than one cycle. This particular problem was studied earlier by Raz and Spieker [17], who showed a lower bound of $\Omega(n\log\log n)$ for non-deterministic protocols even with unbounded rounds of communication. It is easy to see that a protocol for $\mathsf{Conn}_{2n}$ immediately yields a protocol with the same complexity for $\mathsf{HamCycle}(n)$ .

1.1 Our Results

To state our results, we will need the following notation; detailed problem definitions and notation are presented in Section 2. Let $C_{\delta}^{B,r}(f)$ be the $\delta$ -error, $r$ -round randomized communication complexity of the function $f$ when Bob sends the first message; let $C_{\delta}^{A,r}(f)$ be the corresponding complexity when Alice sends the first message. We write $C_{\delta}^{r}(f)$ , omitting the superscript, to denote the complexity when either party is allowed to start. $\log^{(i)}n$ denotes the $i$ -th iterated logarithm of $n$ .

Our lower bound for $C_{\delta}^{2}(\mathsf{Conn}_{n})$ is derived as follows. We show that the pointer chasing problem reduces to the Hamiltonian cycle problem; more precisely, we show (see Theorem 7 in Section 3) that for all $\delta\in[0,1)$ , we have

C_{\delta}^{2}(\mathsf{HamCycle}(n))\geq C_{\delta}^{B,3}(\textsf{bPC}(16n+2,7% )).

We then show that

C_{\delta}^{B,3}(\textsf{bPC}(n,7))=\Omega(n\log n).\qquad\text{ (\lx@cref{% creftype~refnum}{thm:rand-bit} in \lx@cref{creftype~refnum}{subsec:proofrandbi% t})}

Theorem 13 is the main technical contribution of this work. Combining these with our earlier observation that $\mathsf{HamCycle}(n)$ reduces to $\mathsf{Conn}_{2n}$ , we obtain the following.

Theorem 1 (Main Result).

For all $\delta\in[0,1/2)$ , we have

C_{\delta}^{2}(\mathsf{Conn}_{n}),C_{\delta}^{2}(\mathsf{HamCycle}(n))=\Omega(% n\log n).

Typically, pointer chasing has been considered in the setting the number of rounds of communication is $r=k-1$ ; we know of only a few prior works [15, 3] that have considered $r<k-1$ . However, the techniques used in these do not seem to extend to yield an optimal $\Omega(n\log n)$ lower bound.

Furthermore, our reduction can be used to obtain superlinear lower bounds for $\mathsf{Conn}_{n}$ for randomized protocols with more than two rounds of communication. By extending the result [15, Theorem 6] to the randomized setting, we show that for all $\delta\in[0,1/2)$ , constant $k$ and $r\leq k/2-1$

C_{\delta}^{B,r}(\textsf{bPC}(n,k))=\Omega(n\log^{(k-1)}n);

our reduction then implies that for all constant $r$ ,

C_{\delta}^{r}(\mathsf{Conn}_{n})=\Omega\left(\frac{n}{r}\log^{(2r+1)}\frac{n}% {r}\right).

The proof details of the above statement are deferred to the extended version of the paper.

For our main result we used the lower bound for the bit version of the pointer chasing problem, where Alice and Bob need to determine the last bit for $v_{7}$ with just three rounds of communication. We show that for the full version determining $v_{5}$ is already equally hard.

Theorem 2.

For all constants $\delta\in[0,1/2)$ , $C_{\delta}^{B,3}(\textsf{PC}(n,5))=\Omega(n\log n)$ .

Complementing the above, we show that there are deterministic protocols that can chase a larger pointer depth with few rounds, by extending the protocols in [5, 15].

Theorem 3.

Let $k^{\prime}\geq\left\lceil\frac{k+5}{3}\right\rceil$ . Then $C^{B,k^{\prime}}(\textsf{PC}(n,k))=O(nk\log\log n)$ . For the bit-version: $k^{\prime}\geq\left\lceil\frac{k+6}{4}\right\rceil$ . Then $C^{B,k^{\prime}}(\textsf{bPC}(n,k))=O(nk\log\log n)$ .

1.2 Organization of the paper

In Section 3, we describe the reduction from $\textsf{PC}(n,k)$ to $\mathsf{Conn}_{2n}$ (and in particular, the $\mathsf{HamCycle}(n)$ problem).

Section 4 proves Theorem 2, a strong lower bound for the full-version of the pointer chasing problem. Section 5 builds upon the result in Section 4 to prove the main technical result: a strong lower bound for the bit-version Theorem 13. Proofs are detailed in Appendices D and E. Appendix F proves the upper bounds in Theorem 3.

Each technical result is preceded by a proof outline that emphasizes key steps and conceptual insights.

2 Preliminaries

2.1 Problem Definitions

Definition 4 (Pointer Chasing, full-version).

$\textsf{PC}(n,k)$ is the 2-player pointer chasing problem defined as follows: The input instance is a $(k+1)$ -layered, directed graph $G$ . The vertex set is $\mathcal{V}_{0},\mathcal{V}_{1},\ldots,\mathcal{V}_{k}$ , with $|\mathcal{V}_{i}|=n$ for all $i\in\{0,1,2,\ldots,k\}$ . The edges of $G$ are bijections from $\mathcal{V}_{i}$ to $\mathcal{V}_{i+1}$ for each $i\in\{0,1,2,\ldots,k-1\}$ . The edges are distributed between Alice and Bob as follows:

Alice gets bijections $F_{A,i}:\mathcal{V}_{2i-2}\rightarrow\mathcal{V}_{2i-1}$ Bob gets bijections $F_{B,i}:\mathcal{V}_{2i-1}\rightarrow\mathcal{V}_{2i}$

There is a fixed vertex $v_{0}\in\mathcal{V}_{0}$ known to both, and they need to find the unique vertex $v_{k}\in\mathcal{V}_{k}$ at distance $k$ from $v_{0}$ .

Definition 5 (Pointer Chasing, bit-version).

$\textsf{bPC}(n,k)$ is the problem of finding the least significant bit of $v_{k}$ (as opposed to $v_{k}$ in $\textsf{PC}(n,k)$ ). We call the least significant bit of $v_{k}$ the parity of $v_{k}$ (having identified the vertex set with $[n]$ ). This is also called the bit-version of the pointer-chasing problem.

For pointer chasing problems, we require that any valid protocol has both players decide on the same answer and output it after the protocol concludes.

We note that Definition 4 differs slightly from the description given in the introduction: in our formal definition above, we allow a different function (bijection) at every step. It is not difficult to see that the two formulations are equivalent up to a factor- $k$ blowup in the vertex-set size. In particular, any instance satisfying Definition 4 is a special case of the introduction’s definition with $|\mathcal{V}_{A}|=|\mathcal{V}_{B}|=n\lceil(k+1)/2\rceil$ , obtained by taking $\mathcal{V}_{A}=\bigcup_{i:i\bmod 2=0}\mathcal{V}_{i}$ and $\mathcal{V}_{B}=\bigcup_{i:i\bmod 2=1}\mathcal{V}_{i}$ .

Definition 6.

The $\mathsf{HamCycle}(n)$ problem is defined as follows. Let $V_{A}$ and $V_{B}$ be two disjoint sets of $n$ vertices each. Alice receives a bijection map $\sigma_{A}:V_{A}\to V_{B}$ , and Bob receives a bijection $\sigma_{B}:V_{B}\to V_{A}$ . The goal is to decide whether the composition $\sigma_{A}\circ\sigma_{B}$ (equivalently, union of the two perfect matchings) forms a Hamiltonian cycle covering all $2n$ vertices.

For the problems $\mathsf{Conn}_{n}$ , $\mathsf{HamCycle}(n)$ under consideration, following convention, we require only that one of the players knows the answer after $r$ rounds.

2.2 Notation

We use $[n]$ to denote the set $\{1,2,\ldots,n\}$ . Random variables will typically be denoted by capital letters: e.g. $V_{5}$ denotes a random variable, and $V_{5}=v_{5}$ will be its instantiation to the value $v_{5}$ . Most random variables we deal with will be over a finite, discrete domain. The support of a random variable $X$ is denoted by $\mathrm{supp}(X)$ .
All logarithms are to the base 2, and $\log^{(i)}n$ denotes the $i$ -th iterated logarithm of $n$ .
Our proofs make significant use of information theoretic concepts. We describe some preliminaries in Section A.
We assume throughout the proofs that when used, $\varepsilon,\delta$ are sufficiently small constants.

2.3 Communication Complexity preliminaries

We assume some familiarity with basic notions of two-party communication complexity, and refer the reader to standard books [10, 16] for the basics. Let $f:\mathcal{X}\times\mathcal{Y}\rightarrow Z$ be a function.

Rectangles, Subrectangles.

A combinatorial rectangle is a subset of inputs of the form $A\times B$ , where $A\subseteq\mathcal{X}$ and $B\subseteq\mathcal{Y}$ . A deterministic protocol $\Pi=(M_{1},M_{2},\ldots,M_{k})$ splits the input space into a disjoint partition of rectangles, each rectangle corresponding to a certain transcript $(M_{1}=m_{1},M_{2}=m_{2},\ldots,M_{k}=m_{k})$ of the protocol.

We call a rectangle $R^{\prime}$ a subrectangle of a rectangle $R$ if $R^{\prime}\subseteq R$ . $R^{\prime}$ is a subrectangle of the protocol $\Pi$ , if it is a subrectangle of some rectangle in the partition induced by the protocol $\Pi$ . If $R=A\times B$ is a rectangle, then a subrectangle of the form $A^{\prime}\times B$ for $A^{\prime}\subseteq A$ is called a horizontal slice of $R$ . Similarly, $A\times B^{\prime}$ , for $B^{\prime}\subseteq B$ is called a vertical slice.

Let $R=A\times B$ be a rectangle. Let $Z$ be a random variable that depends on the inputs. We denote $Z|R$ to be the random variable having distribution of $Z$ conditioned on inputs restricted to the rectangle $R$ .

3 Lower bounds on $\mathsf{HamCycle}(n)$

Theorem 7.

Let $n$ be a multiple of $4$ . The $\textsf{bPC}(n,k)$ problem reduces to the $\mathsf{HamCycle}(N)$ problem with $N=2+2n(k+1)$ in the two-party communication setting.

Proof.

For notational simplicity, we describe the reduction with only two functions $\sigma_{A}:[n]\rightarrow[n]$ , and $\sigma_{B}:[n]\rightarrow[n]$ in the pointer chasing instance. It will be clear that the reduction can be modified to accommodate the case of different bijections at every level. We specify the reduction for even $k$ , a similar one works for odd $k$ with minor changes.

Let $G$ be the graph for the pointer chasing instance, with permutations $\sigma_{A}:V_{A}\to V_{B}$ and $\sigma_{B}:V_{B}\to V_{A}$ as edges, and a fixed starting vertex $v_{0}\in V_{A}$ . We identify $V_{A}$ and $V_{B}$ with $[n]$ . For notational reasons, we assume that $v_{0}$ is the vertex $2$ in $V_{A}$ . Let $v_{k}$ be the pointer at depth $k$ . We show that Alice and Bob can produce a graph $G^{\prime}$ without communication, such that $G^{\prime}$ is a single cycle if and only if $v_{k}\bmod 2=1$ .

Though the graph $G^{\prime}$ described will be a directed graph, the underlying undirected graph of $G^{\prime}$ (undirected version of $G\textquoteright$ ) will be a Hamiltonian cycle iff $v_{k}\mod 2=1$

We first describe a reduction that produces a graph $\tilde{G}^{\prime}$ satisfying the following: if $v_{k}\bmod 2=1$ , then $\tilde{G}^{\prime}$ is the union of two cycles. If $v_{k}\bmod 2=0$ , then $\tilde{G}^{\prime}$ is the union of four cycles. A slight modification to the edges in this instance will produce an appropriate YES/NO instance of $\mathsf{HamCycle}(N)$ , concluding the reduction.

Vertex set for $\tilde{G^{\prime}}$ .

We define symmetric vertex sets $V_{A}^{\prime}$ and $V_{B}^{\prime}$ forming the bipartite graph $\tilde{G}^{\prime}=(V_{A}^{\prime}\cup V_{B}^{\prime},\tilde{E}^{\prime})$ :

	$\displaystyle V_{A}^{\prime}$	$\displaystyle=\{A_{0}^{\alpha},A_{0}^{\beta}\}\;\cup\;\{A_{t,\ell}^{\alpha},A_% {t,\ell}^{\beta}:t\in[k+1],\ell\in[n]\},$
	$\displaystyle V_{B}^{\prime}$	$\displaystyle=\{B_{0}^{\alpha},B_{0}^{\beta}\}\;\cup\;\{B_{t,\ell}^{\alpha},B_% {t,\ell}^{\beta}:t\in[k+1],\ell\in[n]\}$

We have $(k+1)$ blocks of vertices. Each vertex $v$ in the original $G$ has two copies in each block: an $\alpha$ -copy and a $\beta$ -copy (denoted by superscripts). There are $4$ additional special vertices labeled with block number $0$ for technical reasons. $A_{t,\ell}^{\alpha}$ denotes the $\alpha$ -copy of the vertex $\ell\in V_{A}$ in the $t$ -th block.

We note again that $v_{0}$ was the vertex labeled $2$ in $V_{A}$ in $G$ .

Hence, $|V_{A}^{\prime}|=|V_{B}^{\prime}|=2+2n(k+1),$ and the total number of vertices in $\tilde{G}^{\prime}$ (and $G^{\prime}$ ) is $|V_{A}^{\prime}|+|V_{B}^{\prime}|=4+4n(k+1).$

Alice’s Edges (based on $\sigma_{A}$ ).

$\blacksquare$

Fixed edges: $A_{0}^{\alpha}\to B_{0}^{\alpha},\quad A_{0}^{\beta}\to B_{0}^{\beta}$
$\blacksquare$

Permutation ( $t\in[1,k+1],\ell\in[n]$ ):

$A_{t,\ell}^{\alpha}\to\begin{cases}B_{t,\sigma_{A}(\ell)}^{\alpha},&\text{if }% t\leq\tfrac{k}{2},\\ B_{t,\sigma_{A}^{-1}(\ell)}^{\alpha},&\text{if }t>\tfrac{k}{2}+1\end{cases},% \quad A_{t,\ell}^{\beta}\to\begin{cases}B_{t,\sigma_{A}(\ell)}^{\beta},&\text{% if }t\leq\tfrac{k}{2},\\ B_{t,\sigma_{A}^{-1}(\ell)}^{\beta},&\text{if }t>\tfrac{k}{2}+1\end{cases}$
$\blacksquare$

Critical ( $t=\tfrac{k}{2}+1$ ): $A_{t,\ell}^{\alpha}\to\begin{cases}B_{t,\ell}^{\alpha},&\text{if }\ell\bmod 2=% 0,\\ B_{t,\ell}^{\beta},&\text{if }\ell\bmod 2=1\end{cases},\quad A_{t,\ell}^{\beta% }\to\begin{cases}B_{t,\ell}^{\beta},&\text{if }\ell\bmod 2=0,\\ B_{t,\ell}^{\alpha},&\text{if }\ell\bmod 2=1\end{cases}$

Bob’s Edges (based on $\sigma_{B}$ ).

$\blacksquare$

Fixed: $B_{0}^{\alpha}\to A_{1,v_{0}}^{\alpha},\quad B_{0}^{\beta}\to A_{1,v_{0}}^{\beta}$
$\blacksquare$

Permutation ( $t\in[1,k],\ell\in[n]$ ):

$B_{t,\ell}^{\alpha}\to\begin{cases}A_{t+1,\sigma_{B}(\ell)}^{\alpha},&\text{if% }t\leq\tfrac{k}{2},\\ A_{t+1,\sigma_{B}^{-1}(\ell)}^{\alpha},&\text{if }t>\tfrac{k}{2}\end{cases},% \quad B_{t,\ell}^{\beta}\to\begin{cases}A_{t+1,\sigma_{B}(\ell)}^{\beta},&% \text{if }t\leq\tfrac{k}{2},\\ A_{t+1,\sigma_{B}^{-1}(\ell)}^{\beta},&\text{if }t>\tfrac{k}{2}\end{cases}$

\blacksquare

Block $k{+}1$ to Alice’s first block: $(v_{0}\equiv 2)$

B_{k+1,\ell}^{\alpha}\to\begin{cases}A_{1,\ell+1}^{\alpha},&\text{if }\ell% \notin\{v_{0}{-}1,v_{0},n\},\\ A_{1,v_{0}+1}^{\alpha},&\text{if }\ell=v_{0}{-}1,\\ A_{0}^{\alpha},&\text{if }\ell=v_{0},\\ A_{1,1}^{\alpha},&\text{if }\ell=n\end{cases},\quad B_{k+1,\ell}^{\beta}\to% \begin{cases}A_{1,\ell+1}^{\beta},&\text{if }\ell\notin\{v_{0}{-}1,v_{0},n\},% \\ A_{1,v_{0}+1}^{\beta},&\text{if }\ell=v_{0}{-}1,\\ A_{0}^{\beta},&\text{if }\ell=v_{0},\\ A_{1,1}^{\beta},&\text{if }\ell=n\end{cases}

Claim 8.

If $v_{k}\bmod 2=0$ , $\tilde{G^{\prime}}$ is the union of $4$ cycles.
If $v_{k}\bmod 2=1$ , $\tilde{G^{\prime}}$ is the union of $2$ cycles.

Proof of Claim.

We defer the analysis of the cases to Appendix C. $\hfill\vartriangleleft$

Figure 1: An illustration of typical paths for

k=2

. The solid path is from

v_{0}

, and the dashed path from an arbitrary

\ell\neq v_{0}

. In the above case, both

\alpha

and

\beta

copies of

v_{0}

will lie in the same cycle.

Modification.

The following slight modification that replaces two constant edges in $\tilde{G}^{\prime}$ gives us the desired $G^{\prime}$ :

(Old edges):: $B_{k+1,n}^{\alpha}\rightarrow A_{1,1}^{\alpha}\quad\text{and}\quad B_{0}^{% \alpha}\rightarrow A_{1,v_{0}}^{\alpha},$ we now map
(New edges):: $B_{k+1,n}^{\alpha}\rightarrow A_{1,v_{0}}^{\alpha}\quad\text{and}\quad B_{0}^{% \alpha}\rightarrow A_{1,1}^{\alpha}$ .

These edges are present in different cycles in the Yes instances of $\tilde{G}^{\prime}$ . Splicing merges the two to a single Hamiltonian cycle (and keeps the NO instances disconnected, since at most two edges are modified). $\hfill\blacktriangleleft$

Assuming our main technical result (Theorem 13), the proof of Theorem 1 follows immediately from the above reduction. Note that since $\mathsf{HamCycle}(N)$ is symmetric between Alice and Bob, we can assume without loss of generality that Bob initiates the communication in any protocol solving it.

4 Randomized lower bound for $\textsf{PC}(n,5)$

Theorem 9 (Theorem 2 restated).

For any constant $\delta\in[0,1/2)$ :

C^{(B,3)}_{\delta}(\textsf{PC}(n,5))=\Omega(n\log n)

Proof outline.

For context, we first describe how pointer chasing lower bounds are typically shown via round elimination [13, 20, 15]. For odd $k$ , consider a $k$ -round protocol $\Pi=(M_{1},\ldots,M_{k})$ with low distributional error, where Bob sends $M_{1}$ . Fixing typical values of $M_{1}=m_{1}$ and $V_{1}=v_{1}$ , one shows that $F_{B}(v_{1})$ remains highly variable if $|\Pi|$ is small. Iterating this $k-1$ -times, alternating roles between Alice and Bob each time, we can fix $M_{1},\ldots,M_{k-1}$ and $V_{1},\ldots,V_{k-1}$ while preserving variability in $F_{A}(v_{k-1})$ . Yet Bob must now infer $v_{k}$ with high confidence, contradicting the protocol’s correctness.

The strategy of fixing $v_{i}$ (i.e., looking at a subrectangle with fixed $v_{i}$ ) after round $i$ that helps isolate entropy in $V_{i+1}$ fails when $\Omega(n\log n)$ bits of communication are allowed. For our lower bound for $\textsf{PC}(n,5)$ , we avoid fixing $v_{2}$ , instead allowing it to vary and analyzing a good assignment $\sigma:\mathcal{A}_{2}\to\mathcal{V}_{B}$ , where $\mathcal{A}_{2}\subseteq\mathrm{supp}(V_{2})$ . Under high-entropy $F_{B}\mid m_{1}$ , we show that $V_{4}$ remains variable over $\Omega(n)$ candidates, each with probability $\Omega(1/n)$ . Since $F_{A}\mid m_{2}$ also retains entropy (since $|m_{2}|$ is small), Bob cannot reliably infer the next pointer across these $V_{4}$ ’s. Using an unfixed $V_{2}$ is what allows us to infer that $V_{4}$ is spread out. However, this requires a careful probabilistic analysis in choosing a good $\sigma$ while accounting for correlations across layers. The proof relies on the permutation structure of the functions. We now present the proof. $\hfill\blacktriangleleft$

Proof.

We show that no 3-round deterministic protocol $\Pi=(M_{1},M_{2},M_{3})$ , with Bob starting the communication and using at most $\varepsilon n\log n$ bits exchanged per message for a small constant $\varepsilon>0$ , can correctly solve the problem on more than a (small) constant fraction of inputs drawn from the uniform distribution. The theorem then follows by an application of Yao’s lemma [10, Sec 3.4, Theorem 3.20], followed by standard error reduction techniques via repetition.

Recall notation from Section 2: Alice has functions $f_{A,1}$ on $\mathcal{V}_{0}\rightarrow\mathcal{V}_{1}$ , $f_{A,2}$ on $\mathcal{V}_{2}\rightarrow\mathcal{V}_{3}$ , and $f_{A,3}$ on $\mathcal{V}_{4}\rightarrow\mathcal{V}_{5}$ . Bob has $f_{B,1}$ and $f_{B,2}$ for $\mathcal{V}_{1}\rightarrow\mathcal{V}_{2}$ and $\mathcal{V}_{3}\rightarrow\mathcal{V}_{4}$ respectively. We use $\mathcal{F}_{A}$ and $\mathcal{F}_{B}$ to denote the set of all possible inputs to Alice and Bob respectively.

Let Bob send $M_{1}$ , with $|M_{1}|=\varepsilon_{B}n\log n$ , and Alice send $M_{2}$ , with $|M_{2}|=\varepsilon_{A}n\log n$ . After $M_{2}$ , Bob should know the answer, which he conveys to Alice, using $M_{3}$ . We therefore consider just the first two messages, and show that Bob cannot know the correct answer for a constant fraction of the inputs.

Initially, with no messages passed, we have:

$\blacksquare$

$H[F_{A,1}]=H[F_{A,2}]=H[F_{A,3}]=H[F_{B,1}]=H[F_{B,2}]=\log n!=n\log n-O(n)$
$\blacksquare$

$H[V_{i}]=\log n$ , for all $1\leq i\leq 5$

We prove the theorem in a sequence of three claims, whose proofs we defer to Appendix D.

Claim 10 (Round 1).

With probability $\geq 1/2$ over the choice of inputs, $(M_{1},V_{1})$ satisfy the following:

1.

$H[F_{B,1}(v_{1})|M_{1}=m_{1},V_{1}=v_{1}]\geq(1-12\varepsilon_{B})\log n$
2.

$H[F_{A,2}]\geq n\log n-O(n)$
3.

$H[F_{B,2}\mid M_{1}=m_{1}]\geq(1-4\varepsilon_{B})n\log n$

Proof.

Deferred to Appendix D. $\hfill\vartriangleleft$

We note that fixing such a pair of $(m_{1},v_{1})$ gives us a subrectangle of the protocol after $m_{1}$ . For any such subrectangle, we show the following:

Claim 11 (Main Claim).

For a subrectangle $R\subseteq\mathcal{F}_{A}\times\mathcal{F}_{B}$ formed by fixing $(m_{1},v_{1})$ satisfying the conditions in Claim 10, the following is true: There exists a set $\mathcal{A}_{4}:=\{b_{1},b_{2},\ldots,b_{r}\}\subseteq\mathcal{V}_{4}$ , for $r\geq n/6$ , and a constant $c_{1}$ such that with probability $\geq 1-n\exp(-c_{1}n^{1-O(\varepsilon_{B})})=1-o(1)$ over choice of $F_{A,2}\sim R$ :

\forall i\in[r]:\qquad\Pr_{f_{B}\sim R}\left[V_{4}=b_{i}\mid f_{A,2}\right]% \geq\frac{1}{20n}

(1)

Proof.

Deferred to Appendix D. $\hfill\vartriangleleft$

Let $\sigma\coloneq F_{A,2}$ restricted to the domain $\mathrm{supp}(V_{2})$ . As mentioned in the outline, the proof of Claim 11 goes via analyzing a random assignment $\sigma:\mathrm{supp}(V_{2})\rightarrow\mathcal{V}_{3}$ under $F_{A,2}$ . We proceed to analyze what happens in the subrectangle of a fixed $\sigma$ that satisfies (1) from Claim 11, after Round 2 (i.e. after Alice sends $M_{2}$ ). We note that once we fix a $\sigma$ , it corresponds to a class of $F_{A}$ ’s, and hence a subrectangle within the rectangle $R$ in Claim 11.

Claim 12 (Error after Round 2).

Consider a subrectangle $R^{\prime}\subseteq R\subseteq\mathcal{F}_{A}\times\mathcal{F}_{B}$ caused by fixing a $\sigma=\sigma^{*}$ satisfying (1) in Claim 11. In any such rectangle $R^{\prime}$ , Bob makes an error in knowing the answer with probability at least $1/400$ , after receiving Alice’s message $M_{2}$ .

Proof.

Deferred to Appendix D. $\hfill\vartriangleleft$

We finally collate the errors across the subrectangles from Claims 10, 11 and 12. The overall error of the protocol is at least:

\Pr(\text{Error })\geq\frac{1}{2}\cdot\left(1-n\exp\left(-c_{1}n^{1-O(% \varepsilon_{B})}\right)\right)\cdot\frac{1}{400}=\Omega(1)\

$\hfill\blacktriangleleft$

5 Randomized lower bound for $\textsf{bPC}(n,7)$

5.1 Proof of main result

Theorem 13.

For any constant $\delta\in[0,1/2)$ ,

C^{(B,3)}_{\delta}(\textsf{bPC}(n,7))=\Omega(n\log n)

Proof Outline.

Before giving the proof, we give a rough outline of the steps involved.

We start with a sub-rectangle $R^{\prime}$ of the protocol as described in Claim 12, where $m_{1},v_{1},\sigma$ are fixed. We have $\Omega(n)$ possibilities for $V_{4}$ at this point, called $b_{1},\ldots,b_{r}$ . From Bob’s point of view, within the rectangle $R^{\prime}$ , he exactly knows $V_{4}$ ; suppose that $V_{4}=b_{1}$ .

On receiving $m_{2}$ , Bob will know the shadow of $b_{1}$ : the set $\Delta(b_{1})\coloneq\{f_{A,3}(b_{1}):f_{A,3}\in R^{\prime}\}$ , which typically has size $\approx n^{1-\varepsilon_{A}}$ . For the full-version, this was sufficient to prevent Bob from knowing $V_{5}$ , but it is not clear that the parity of $V_{7}$ reachable from potential $V_{4}$ ’s will vary within the shadow. Indeed, if the goal was to find parity of $V_{5}$ , Alice could explicitly send this information to Bob in $O(n)$ bits with $m_{2}$ (by sending parity $(F_{A,3}(i))$ for every $i\in[n]$ ). The extra layers in the instance come into play here: when looking at the parity of $V_{7}$ , even if Alice sends the last bit (or more) of $f_{A,\star}(i)$ to Bob, due to the high entropy of intermediate layers, we show that the composed function $\textrm{parity}(F_{A,4}(f_{B,3}(F_{A,3}(b_{j})))$ is still unpredictable to Bob within the shadow $\Delta(b_{j})$ .

Following [15], we view the parity of a vertex in the set $\mathcal{V}_{7}$ as a two-coloring $\chi_{7}:\mathcal{V}_{7}\rightarrow\{0,1\}$ . For a given set of inputs, $f_{A},f_{B}$ , this induces two-colorings on higher levels: $\chi_{6}\coloneq\chi_{7}\circ f_{A,4}$ , $\chi_{5}\coloneq\chi_{6}(f_{B,3})$ . If the intermediate functions are viewed as random, the resulting coloring at each layer is also a random coloring.

In terms of two-colorings, it is sufficient to show that within $R^{\prime}$ , $\Delta(b_{1})\subseteq\mathcal{V}_{5}$ is two-colored by $\chi_{5}$ in a roughly balanced way while varying over the inputs consistent with the current subrectangle. We formally show this in the proof via a composition lemma. This is a major technical contribution of our work, and we elaborate on it in Appendix E.

$\hfill\blacktriangleleft$

Figure 2: Fixing

(m_{1},v_{1},\sigma)

, Bob knows

V_{4}

exactly, say

V_{4}=b_{j}

.

\Delta(b_{j})

will be two-colored by

\chi_{6}\circ F_{B,3}|b_{j}

by most

F_{B,3}|b_{j}

(by composition lemma), preventing Bob from knowing the answer.

Proof.

We assume, as before, that all input functions come from the uniform distribution over respective domains and show that any protocol communicating $\varepsilon n\log n$ bits will err on a (small) constant fraction of the inputs (for small enough $\varepsilon$ ).

We follow the proof of Theorem 9 and arrive at a rectangle $R^{\prime}$ as in Claim 11. This gives a set $\mathcal{A}_{4}=\{b_{1},b_{2},\ldots,b_{r}\}\subseteq\mathcal{V}_{4}$ , of size $r\geq n/6$ for some fixed $m_{1},v_{1},\sigma$ .

Compared to the full-version, we have two extra layers of functions: $F_{B,3},F_{A,4}$ . The fixing of $m_{1},v_{1},\sigma$ does not affect $F_{A,4}$ , and the effect on $F_{B,3}$ is described by $H[F_{B,3}\mid R^{\prime}]\geq(1-4\varepsilon_{B})n\log n$ from Claim 10.

Due to correlations induced by the message $m_{1}$ , the possibilities for function $f_{B,3}$ between $\mathcal{V}_{5},\mathcal{V}_{6}$ are influenced by what $V_{4}$ is. In particular, let $F_{B,3}^{m_{1},b_{j}}\coloneq F_{B,3}|R^{\prime},V_{4}=b_{j}$ . We first show that many of the $b_{j}\in\mathcal{A}_{4}$ ensure a high entropy of $F_{B,3}^{m_{1},b_{j}}$ .

Claim 14.

There exists $\mathcal{A}_{4}^{\prime}\subseteq\mathcal{A}_{4}$ and constants $c_{1}>1,\alpha_{1}\in(0,1)$ satisfying:

1.

$\forall b_{j}\in\mathcal{A}_{4}^{\prime}\quad\nobreak\ :\nobreak\ \quad H[F_{B% ,3}|R^{\prime},V_{4}=b_{j}]\geq(1-c_{1}\varepsilon_{B})n\log n$
2.

$|\mathcal{A}_{4}^{\prime}|\geq\alpha_{1}n$

Proof.

Deferred to Appendix E. $\hfill\vartriangleleft$

We now invoke the following Composition Lemma, whose proof is given in the extended version of this paper.

Lemma 15 (Composition Lemma).

Let $F:[n]\rightarrow[n]$ be a (random) function satisfying $H[F]\geq(1-\varepsilon)n\log n$ . Let $\chi:[n]\rightarrow\{0,1\}$ be a random, balanced two-coloring of $[n]$ . Then, $\exists J\subseteq[n]$ with $|J|\geq(1-\sqrt{\varepsilon})n$ such that for any distribution $D$ on $J$ , with $H_{\infty}[D]\geq k$ , with probability $\geq 1-1/n^{3}$ over choice of $\chi$ , the composed function $X_{i}\coloneq\chi\circ F(i)$ satisfies:

\Pr_{F}\left(\left|\sum_{i}D(i)X_{i}-\frac{1}{2}\right|\geq 10\varepsilon^{1/3% 2}+t\right)\leq 4\varepsilon^{1/32}+\frac{1}{\varepsilon^{1/32}}\cdot\exp(-% \Omega(t^{2}\cdot 2^{k}))

Proof.

Deferred to the extended version of this paper. $\hfill\blacktriangleleft$

Invoke the lemma for each $b_{i}\in\mathcal{A}_{4}^{\prime}$ in turn, setting $F\equiv F_{B,3}^{m_{1},b_{i}}$ (and $\varepsilon=c_{1}\varepsilon_{B}$ , where $c_{1}$ is the constant from Claim 14), and random choice of $\chi\equiv\chi_{6}:\mathcal{V}_{6}\rightarrow\{0,1\}$ . Call a $\chi_{6}$ nice, if it ensures the result of Lemma 15 for every $b_{i}\in\mathcal{A}_{4}^{\prime}$ . By a union bound, a random $\chi_{6}$ is nice with probability $\geq 1-\frac{1}{n}$ .

Fix a nice $\chi_{6}$ , this forms a subrectangle $R^{\prime\prime}$ of $R^{\prime}$ , being a restriction of $F_{A,4}$ . For each such nice $\chi_{6}$ , we get sets $J_{1},\ldots,J_{r^{\prime}}\subseteq\mathcal{V}_{5}$ , with $|J_{i}|\geq(1-\sqrt{c_{1}\varepsilon_{B}})n$ , for every $i\in[r^{\prime}]$ . It now remains to show that a typical $b_{i}$ has a large shadow within $J_{i}$ after $m_{2}$ . The following claim shows that this happens with good probability. The proof is deferred to Appendix E.

Claim 16.

Let $\gamma:=\sqrt{c_{1}\varepsilon_{B}}$ . Let $\mathcal{A}_{4}^{\prime}\coloneq\{b_{1},\ldots,b_{r}\}\subseteq\mathcal{V}_{4}$ with $r\geq\alpha_{1}n$ , as in ˜14. For each $i\in[r]$ , let $J_{i}\subseteq\mathcal{V}_{5}$ be sets with $|J_{i}|\geq(1-\gamma)n$ . Define the events $\mathcal{E}_{i}:=\{F_{A,3}(b_{i})\in J_{i}\}$ , for each $i\in[r]$ .

Then, there exist a partitioning of $R^{\prime\prime}$ into subrectangles $\{R^{\prime\prime}_{(m_{2},z)}\}_{m_{2}\in\mathrm{supp}(M_{2}),z\in\{0,1\}^{r}}$ (where $m_{2}$ is Alice’s message and $z$ is a function of $F_{A,3}$ alone) and constant $\alpha_{2}>0$ such that with probability at least $1/8$ over choice of $M_{2}=m_{2}$ and $z$ , we have: at least $\alpha_{2}n$ elements $b_{i}^{*}\in\mathcal{A}$ satisfy:

H\!\left[F_{A,3}(b_{i}^{*})\,\middle|\,M_{2}=m_{2},Z=z,\mathcal{E}_{i}\right]% \;\;\geq\;\;(1-4\sqrt{\varepsilon_{A}})\log n,

Choose a $(m_{2},z)$ to fix a sub-rectangle $\tilde{R}:=R^{\prime\prime}_{(m_{2},z)}\subseteq R^{\prime\prime}$ (a horizontal slice in $R^{\prime\prime}$ ) that satisfies the conclusion of ˜16. $(\chi_{6},m_{2},z)$ are fixed here. Let $S^{*}\coloneq\{b_{i_{1}}^{*},b_{i_{2}}^{*}\ldots,b_{i_{\ell}}^{*}\}$ be the indices in $\mathcal{A}_{4}^{\prime}$ arising out of Claim 16. We have $\Pr(S^{*})\geq\alpha_{2}n\times 1/20n=\alpha_{2}/20$ .

Let $D^{\prime}_{j}$ be the distribution $F_{A,3}(b_{i_{j}}^{*})|\tilde{R}$ ; we have $H[D_{j}^{\prime}]\geq(1-4\sqrt{\varepsilon_{A}})\log n$ . Set $\delta^{\prime}$ to be $\varepsilon_{A}^{1/32}$ ; by Lemma 17 (Appendix B), $D_{j}^{\prime}$ is within $\delta^{\prime}$ in $\ell_{1}$ distance of a distribution $D_{j}$ such that $H_{\infty}[D_{j}]\geq(1-4\sqrt{\varepsilon_{A}}/\delta^{\prime})\log n$ .
Fix a good $b_{j}\in\mathcal{A}_{4}^{\prime}$ (a vertical slice in $\tilde{R}$ ).
Set $t=10\varepsilon^{{1}/{32}}$ , $\delta\coloneq 4\sqrt{\varepsilon_{A}}/\delta^{\prime}$ in Lemma 15. We conclude that $\chi_{6}\circ F_{B,3}^{b_{j}}|\tilde{R}$ two-colors $D_{j}$ with bias $\eta\leq 20\varepsilon^{1/32}$ with probability (over $F_{B,3}^{b_{j}}|\tilde{R})$ of at least $\beta\coloneq(1-5\varepsilon^{1/32})$ . (Recall that $\varepsilon=c_{1}\varepsilon_{B}$ .) This means it colors $D_{j}^{\prime}$ with bias at most $\eta_{2}\coloneq\eta+\delta^{\prime}=\eta+\varepsilon_{A}^{1/32}$

Call an $f_{B,3}$ good if it ensures a bias of at most $\eta_{2}$ in $R^{\prime\prime}$ . On such $f_{B,3}$ , a deterministic $0$ or $1$ answer from Bob makes an error with probability at least $1/2-\eta_{2}$ .

The overall probability of error, is, therefore:

\Pr[\textrm{Error}]\geq\left(\frac{1}{2}-\eta_{2}\right)\times\frac{\alpha_{2}% }{20}\times\frac{1}{8}\times\left(1-\frac{1}{n}\right)\times\beta=\Omega(1)

This concludes the proof of Theorem 13. $\hfill\blacktriangleleft$

References

[1] Simon Apers, Yuval Efron, Paweł Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, and Danupon Nanongkai. Cut query algorithms with star contraction. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 507–518. IEEE, 2022.
[2] Sepehr Assadi. Recent advances in multi-pass graph streaming lower bounds. ACM SIGACT News, 54(3):48–75, 2023. doi:10.1145/3623800.3623808.
[3] Sepehr Assadi, Gillat Kol, Raghuvansh R Saxena, and Huacheng Yu. Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 354–364. IEEE, 2020. doi:10.1109/FOCS46700.2020.00041.
[4] László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 337–347. IEEE, 1986.
[5] Carsten Damm, Stasys Jukna, and Jiří Sgall. Some bounds on multiparty communication complexity of pointer jumping. Computational Complexity, 7(2):109–127, 1998. doi:10.1007/PL00001595.
[6] Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.
[7] András Hajnal, Wolfgang Maass, and György Turán. On the communication complexity of graph properties. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 186–191, 1988. doi:10.1145/62212.62228.
[8] Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf. New bounds on the classical and quantum communication complexity of some graph properties. In 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science, page 148, 2012.
[9] Bala Kalyanasundaram and Georg Schintger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545–557, 1992. doi:10.1137/0405044.
[10] Eyal Kushilevitz. Communication complexity. In Advances in Computers, volume 44, pages 331–360. Elsevier, 1997. doi:10.1016/S0065-2458(08)60342-3.
[11] Xinyu Mao, Guangxu Yang, and Jiapeng Zhang. Gadgetless lifting beats round elimination: Improved lower bounds for pointer chasing. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325 of Leibniz International Proceedings in Informatics (LIPIcs), pages 75:1–75:14, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2025.75.
[12] Colin McDiarmid. On the method of bounded differences. Surveys in combinatorics, 141(1):148–188, 1989.
[13] Noam Nisan and Avi Widgerson. Rounds in communication complexity revisited. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 419–429, 1991. doi:10.1145/103418.103463.
[14] Christos H Papadimitriou and Michael Sipser. Communication complexity. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 196–200, 1982. doi:10.1145/800070.802192.
[15] Stephen J Ponzio, Jaikumar Radhakrishnan, and Srinivasan Venkatesh. The communication complexity of pointer chasing. Journal of Computer and System Sciences, 62(2):323–355, 2001. doi:10.1006/JCSS.2000.1731.
[16] Anup Rao and Amir Yehudayoff. Communication complexity: and applications. Cambridge University Press, 2020.
[17] Ran Raz and Boris Spieker. On the “log rank”-conjecture in communication complexity. Combinatorica, 15(4):567–588, 1995.
[18] Alexander A Razborov. On the distributional complexity of disjointness. In International Colloquium on Automata, Languages, and Programming, pages 249–253. Springer, 1990. doi:10.1007/BFB0032036.
[19] Xiaoming Sun and David P Woodruff. Tight bounds for graph problems in insertion streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), pages 435–448. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.435.
[20] Amir Yehudayoff. Pointer chasing via triangular discrimination. Combinatorics, Probability and Computing, 29(4):485–494, 2020. doi:10.1017/S0963548320000085.

Appendix A Information Theory Preliminaries

Let $X$ be a discrete random variable over a domain $\mathcal{X}$ . The entropy of $X$ is defined by $H[X]\coloneq-\sum_{x\in\mathrm{supp}(X)}\Pr(X=x)\log\Pr(X=x)$ It is always true that $H[X]\leq\log|\mathrm{supp}(X)|$ . If $\sigma$ is a random permutation, then $H[\sigma]=\log n!=n\log n-O(n)$ .

The conditional entropy of a random variable $Y$ given $X$ is defined by

H[Y|X]\coloneq\sum_{x\in\mathrm{supp}(X)}\Pr[X=x]H[Y|X=x]=\operatorname{% \mathbb{E}}_{x}[H[Y_{x}]]

Here, $Y_{x}$ denotes the random variable with distribution $\Pr[Y_{x}=y]=\Pr[Y=y|X=x]$

The min-entropy of a random variable $X$ is defined as: $H_{\infty}[X]=\max_{x\in\mathrm{supp}(X)}\log\frac{1}{\Pr[X=x]}$ .

Properties of Entropy.

1.

Non-negativity: $H(X)\geq 0$ , $H_{\infty}(X)\geq 0$ .
2.

Bounds: $H_{\infty}(X)\leq H(X)\leq\log|\mathcal{X}|$ .
3.

Chain rule: $H(X,Y)=H(X)+H(Y\mid X)$ .
4.

Conditioning: $H(Y\mid X)\leq H(Y)$ .
5.

Data processing: If $Y=f(X)$ then $H(Y)\leq H(X)$ and $H_{\infty}(Y)\leq H_{\infty}(X)$ .
6.

Subadditivity: $H(X,Y)\leq H(X)+H(Y)$ .

Fact 16.0.1 (Fano’s Inequality).

Let $X$ be a random variable taking values in a finite set $\mathcal{X}$ , and let $\hat{X}$ be an estimate of $X$ based on some observation $Y$ . Define the probability of error as

P_{e}=\Pr[\hat{X}\neq X].

Then,

H(X|Y)\leq h(P_{e})+P_{e}\log(|\mathcal{X}|-1),

where $H(X|Y)$ is the conditional entropy of $X$ given $Y$ , and $h(p)=-p\log p-(1-p)\log(1-p)$ is the binary entropy function.

Appendix B Statements and proofs of lemmas used

Lemma 17.

Let $\mu$ be a distribution over $[n]$ , and $X\sim\mu$ . If $H[X]\geq\log n-A$ for some $A\geq 0$ , Then for any $\delta\in(0,1)$ , there exist distributions $\mu_{1},\mu_{2}$ over $[n]$ such that

\mu=\delta\cdot\mu_{1}+(1-\delta)\cdot\mu_{2},

where

H_{\infty}(\mu_{2})\geq\log n-\frac{A+1}{\delta}

Proof.

Set

\theta:=\frac{2^{(A+1)/\delta}}{n},\qquad B:=\{i\in[n]:\mu(i)>\theta\}.

We claim $\mu(B)\leq\delta$ . Suppose, for the sake of contradiction, that $\mu(B)>\delta$ . Let $\mathbbm{1}_{[B]}$ denote the indicator random variable of the event that $X\in B$ . We have:

	$\displaystyle H[X]$	$\displaystyle\leq H[X,\mathbbm{1}_{[B]}]=H[\mathbbm{1}_{[B]}]+H[X\|\mathbbm{1}_% {[B]}]$
		$\displaystyle\leq\nobreak\ 1+\mu(B)\Bigl(\sum_{i\in[B]}\frac{\mu(i)}{\mu(B)}% \log\frac{\mu(B)}{\mu(i)}\Bigr)+\bigl(1-\mu(B)\bigr)\log n$
		$\displaystyle\leq\nobreak\ 1+\mu(B)\Bigl(\log n-\tfrac{A+1}{\delta}\Bigr)+% \bigl(1-\mu(B)\bigr)\log n+\mu(B)\log\mu(B)$
		$\displaystyle=\log n+1-\mu(B)\left(\frac{A+1}{\delta}\right)+\mu(B)\log\mu(B)$
		$\displaystyle<\log n-A,\qquad\ldots\text{if $\mu(B)>\delta$}$

contradicting the assumption $H[X]\geq\log n-A$ .

Let $\mu(B)\coloneq\delta^{\prime}<\delta$ . Let $\mu_{1}\coloneq\mu_{|B}$ , and $\mu_{2}\coloneq\mu_{|B^{c}}$ . Then, clearly, $\mu=\delta^{\prime}\mu_{1}+(1-\delta^{\prime})\mu_{2}$ .
Since $\delta>\delta^{\prime}$ , we can write:

	$\displaystyle\mu$	$\displaystyle=(1-\delta)\mu_{2}+(\delta-\delta^{\prime})\mu_{2}+\delta^{\prime% }\mu_{1}$
		$\displaystyle=(1-\delta)\mu_{2}+\delta\mu_{1}^{\prime}$

Where $\mu_{1}^{\prime}$ is the normalized version of $(\delta-\delta^{\prime})\mu_{2}+(\delta^{\prime})\mu_{1}$ . $\hfill\blacktriangleleft$

Lemma 18 (Entropy vs. Min-Entropy [15]).

Let $D$ be a distribution on $[n]$ with entropy at least $\log n-A$ . Then, for all $\varepsilon>0$ , $D$ is within $\varepsilon$ of a distribution with min-entropy at least

\log n-\frac{A+1}{\varepsilon}.

Theorem 19 ((The method of averaged bounded differences),[12], [6, Corollary 5.1]).

Let $X_{1},\dots,X_{n}$ be random variables and $f$ a function such that for each $i\in[n]$ there exists $c_{i}\geq 0$ with

\bigl|\mathbb{E}[f\mid X_{1},\dots,X_{i-1},X_{i}=a_{i}]-\mathbb{E}[f\mid X_{1}% ,\dots,X_{i-1},X_{i}=a_{i}^{\prime}]\bigr|\leq c_{i}

for all choices of $a_{i},a_{i}^{\prime}$ . Then, for any $t\geq 0$ ,

\Pr\!\left(|f-\mathbb{E}[f]|\geq t\right)\leq 2\exp\!\left(-\tfrac{2t^{2}}{% \sum_{i=1}^{n}c_{i}^{2}}\right).

Appendix C Missing proofs from Section 3

Proof of Claim 8.

We begin with the following observation:

Observation 20.

For a vertex $v^{\prime}\in V_{A}^{\prime}$ , and $j\in\mathbb{N}$ , let $w_{j}(v^{\prime})$ denote the unique vertex at distance $j$ from $v^{\prime}$ . Then, for all $i\in[n]$ ,

	$\displaystyle w_{2k+1}(A_{1,i}^{\alpha})$	$\displaystyle\nobreak\ =\nobreak\ \begin{cases}B_{k+1,i}^{\beta},&\text{if }w_% {k}(A_{1,i}^{\alpha})\bmod 2=1,\\ B_{k+1,i}^{\alpha},&\text{if }w_{k}(A_{1,i}^{\alpha})\bmod 2=0\end{cases},$
	$\displaystyle w_{2k+1}(A_{1,i}^{\beta})$	$\displaystyle\nobreak\ =\nobreak\ \begin{cases}B_{k+1,i}^{\alpha},&\text{if }w% _{k}(A_{1,i}^{\beta})\bmod 2=1,\\ B_{k+1,i}^{\beta},&\text{if }w_{k}(A_{1,i}^{\beta})\bmod 2=0\end{cases}$

Given Obs 20, we analyze each case:

$\blacksquare$

YES Case: (When $v_{k}\bmod 2=1$ )

Chasing the pointer starting at the $\alpha$ -copy vertex $A^{\alpha}_{1,v_{0}}$ , if $v_{k}\mod 2=1$ , then after the $k/2$ -th layer, it switches to a path on the $\beta$ block vertices, ending up at $B^{\beta}_{k+1,v_{0}}$ . This switch triggers a path back such that $A^{\alpha}_{1,v_{0}}$ and $A^{\beta}_{1,v_{0}}$ end up on the same cycle, call it $C_{1}$ .

Now consider following the outgoing edges sequentially (chasing the pointer) starting any of the remaining vertices $A_{1,\star}^{\alpha}$ . Since $n/2$ is even and all functions are permutations, an odd number of them will switch from $\alpha$ to a copy vertex $\beta$ in the layer $k/2$ when following outgoing edges. The edges are set up for the vertex $A_{1,\ell}^{\star}$ to lead back to $A_{1,\ell+1}^{\star}$ , so we eventually visit all the vertices.

Due to this, the remaining edges will form a single second cycle $C_{2}$ . In this cycle, the vertices of $A_{1,\star}^{\star}$ appear in the order $A_{1,1}^{\star}\rightsquigarrow A_{1,3}^{\star}\rightsquigarrow A_{1,4}^{\star}\ldots$ .
$\blacksquare$

NO Case: (When $v_{k}\bmod 2=0$ )
In this case, $A^{\alpha}_{1,v_{0}}$ and $A^{\beta}_{1,v_{0}}$ end up in 2 separate cycles since they do not switch from $\alpha$ to $\beta$ or vice versa.

By a similar argument as above, chasing pointers from the remaining vertices $A_{1,\star}^{\alpha}$ , an even number of them switch from $\alpha$ to a $\beta$ copy at layer $k/2$ when following pointers. This implies that $A^{\alpha}_{1,\ell}$ and $A^{\beta}_{1,\ell}$ cannot fall in the same cycle.

$\hfill\vartriangleleft$

Appendix D Missing proofs from Section 4

Proof of Claim 10

Proof of Claim 10.

Since $|M_{1}|\leq\varepsilon_{B}n\log n$ , $H\left[F_{B}\mid M_{1}\right]\geq(2-\varepsilon_{B})\nobreak\ n\log n$ . ⁵⁵5We take the lower order $O(n)$ terms due to the functions being permutations as subsumed in the larger $\varepsilon_{B}n\log n$ term due to $M_{1}$ for clarity.

By Markov’s inequality, we have

\Pr_{m_{1}}\left(H\left[F_{B}\mid M_{1}=m_{1}\right]\geq(2-4\varepsilon_{B})n% \log n\right)\geq\frac{3}{4},

so for at least $\frac{3}{4}$ of all $f_{B}$ , the first message $M_{1}=m_{1}$ satisfies

H[F_{B}^{m_{1}}]\coloneq H\left[F_{B}\mid M_{1}=m_{1}\right]\geq(2-4% \varepsilon_{B})n\log n.

For such any $m_{1}$ , we therefore have: $H\left[F_{B,j}\mid M_{1}=m_{1}\right]\geq(1-4\varepsilon_{B})n\log n$ , for $j=1,2$ .

Since $H[F_{B,1}^{m_{1}}]\geq(1-4\varepsilon_{B})n\log n$ , subadditivity of entropy implies that $\operatorname{\mathbb{E}}_{i\in[n]}[H[F_{B,1}|{M_{1}=m_{1}}]]\geq(1-4% \varepsilon_{B})\log n$ . Applying Markov’s inequality yields that at least $2n/3$ of $i\in[n]$ satisfy $H[F_{B,1}^{m_{1}}(i)]\geq(1-12\varepsilon_{B})\log n$ .

Call a $v_{1}\in\mathcal{V}_{1}$ good for $m_{1}$ , if $H[F_{B,1}^{m_{1}}(i)]\geq(1-12\varepsilon_{B})\log n$ . Since the distribution of $V_{1}$ is uniform, rectangles corresponding to pairs $(m_{1},v_{1})$ with $M_{1}=m_{1}$ and good $v_{1}$ cover at least a fraction $\frac{3}{4}\times\frac{2}{3}=\frac{1}{2}$ of the total inputs. $\hfill\vartriangleleft$

Proof of Claim 11

Proof of Claim 11.

Define $\mathcal{A}_{2}\coloneq\mathrm{supp}(V_{2})=\{a_{1},\ldots,a_{\ell}\}$ . Let $F_{B,2}^{m_{1},a_{j}}$ denote a random variable following the distribution of $F_{B,2}$ conditioned on $M_{1}=m_{1},V_{2}=a_{j}$ .

Let $\mu_{B}$ be the distribution induced over $\mathcal{A}_{2}$ (equivalently, $V_{2}$ ) in $R$ . We know from Claim 10 that $H[\mu_{B}]=H\left[V_{2}\mid M_{1}=m_{1},V_{1}=v_{1}\right]\geq(1-12\varepsilon% _{B})\log n$ .

Since $H\left[F_{B,2}|{M_{1}=m_{1}}\right]\geq(1-4\varepsilon_{B})n\log n$ , we have that $H\left[F_{B,2}|{M_{1}=m_{1},V_{2}}\right]\geq(1-4\varepsilon_{B})n\log n-\log n% \geq(1-4.5\varepsilon_{B})n\log n$ .

By Markov’s inequality, with probability $\geq 1/2$ over choices for $V_{2}$ , it holds that $H[F_{B,2}^{m_{1},a_{j}}]\geq(1-9\varepsilon_{B})n\log n$ .

Call $\mathcal{A}_{2}^{\prime}:=\{a_{j}\in\mathcal{A}_{2}:H[F_{B,2}^{m_{1},a_{j}}]% \geq(1-9\varepsilon_{B})n\log n\}$ ; the above implies $\mu_{B}(\mathcal{A}_{2}^{\prime})\geq 1/2$ .

Figure 3: Most

\sigma

’s confer good probability mass on

i

, if

F_{B,2}^{-1}(i)

between

\mathcal{V}_{4}

,

\mathcal{V}_{3}

has high entropy.

Definition 21.

$\blacksquare$

Call a vertex $i\in V_{4}$ is locally good with respect to $a_{j}\in\mathcal{A}_{2}^{\prime}$ if

$H[F_{B,2}^{-1}(i)\mid M_{1}=m_{1},V_{2}=a_{j}]\geq(1-36\varepsilon_{B})\log n$
$\blacksquare$

$i\in V_{4}$ is globally good if it is locally good for at least $\frac{1}{4}$ of $\mathcal{A}_{2}$ under $\mu_{B}$ .

Claim 22.

Each $a_{j}\in\mathcal{A}_{2}^{\prime}$ has at least $3n/4$ locally good vertices $i\in\mathcal{V}_{4}$ with respect to it.

Proof.

Since $H[F_{B,2}^{-1}\mid m_{1},a_{j}]\geq(1-9\varepsilon_{B})\log n$ , by sub-additivity we have:

\operatorname{\mathbb{E}}_{i\in[n]}[H[F_{B,2}^{-1}(i)\mid m_{1},a_{j}]]\geq(1-% 9\varepsilon_{B})\log n

The statement follows by Markov’s inequality on $\log n-H[F_{B,2}^{-1}(i)\mid m_{1},a_{j}]$ . $\hfill\vartriangleleft$

Claim 23.

The number of globally good $i\in\mathcal{V}_{4}$ is at least $\frac{n}{6}$ .

Proof.

Let $s$ be the number of globally good $i\in\mathcal{V}_{4}$ . Since every $a_{j}\in\mathcal{A}_{2}^{\prime}$ has at least $3n/4$ locally good vertices, and $\mathcal{A}_{2}^{\prime}$ has measure at least $1/2$ under $\mu_{B}$ , we have:

s\cdot 1+(n-s)\cdot\frac{1}{4}\geq\frac{3n}{4}\cdot\frac{1}{2}

Rearranging gives the stated bound on $s$ . $\hfill\vartriangleleft$

We now make a probabilistic argument to continue the proof of Claim 11. Let $\sigma:\mathcal{A}_{2}\rightarrow\mathcal{V}_{3}$ be a random one-to-one mapping induced by $F_{A,2}$ . Define:

\nu_{B}(r\to i\mid j)\coloneq\Pr_{F_{B,2}}\left[F_{B,2}^{-1}(i)=r\mid m_{1},v_% {1},V_{2}=a_{j}\right]

For each globally good $i\in\mathcal{V}_{4}$ , define the random variable:

Z(i):=\sum_{j=1}^{\ell}\mu_{B}(a_{j})\sum_{r=1}^{n}\mathbf{1}_{\{\sigma(a_{j})% =r\}}\,\nu_{B}(r\to i\mid j),

$Z(i)$ captures the probability mass (under $F_{B}$ ) that fixing a $\sigma$ leads to $V_{4}=i$ . We note that $Z(i)$ is random purely due to the random assignment $\sigma$ , which is completely determined by $F_{A,2}$ . Furthermore, $F_{A,2}$ is a uniformly random permutation in the subrectangle $R$ under consideration, so $\sigma$ is a uniformly random one-to-one mapping.

Claim 24.

For any constant $\gamma\in(0,1)$ , and any globally good $i\in\mathcal{V}_{4}$ as in Definition 21,

\Pr_{\sigma}\left[Z(i)\leq\frac{1-\gamma}{16n}\right]\leq n\exp\left(-2\gamma^% {2}n^{1-O(\varepsilon_{B})}\right),

Proof.

Partition the indices $j\in[\ell]$ into

J_{\text{good}}:=\{j\in[\ell]:i\text{ is locally good for }a_{j}\},\quad J_{% \text{bad}}:=[\ell]\setminus J_{\text{good}},

with $\mu_{B}(a_{J_{\text{good}}})\geq 1/4$ , since $i$ is globally good.

Let $S=\{j\in[\ell]:\mu_{B}(a_{j})\leq n^{-(1-100\varepsilon_{B})}\}$ . From a calculation as in Lemma 17 (Appendix B) with $\delta=1/8$ , $A=12\varepsilon_{B}\log n$ applied on the distribution $\mu_{B}$ (recall that $H[\mu_{B}]\geq(1-12\varepsilon_{B})\log n$ ) , we infer that $\mu_{B}(a_{j}:j\in S^{c})\leq 1/8$ . This implies that:

\sum_{j\in{J_{\text{good}}\cap S}}\mu_{B}(a_{j})\geq 1/4-1/8=1/8

(2)

We can thus write:
$Z(i)=\sum_{j\in J_{\text{good}}\cap S}\mu_{B}(a_{j})\sum_{r=1}^{n}\mathbf{1}_{% \{\sigma(a_{j})=r\}}\,\nu_{B}(r\to i\mid j)+\sum_{j\notin J_{\text{good}}\cap S% }\mu_{B}(a_{j})\sum_{r=1}^{n}\mathbf{1}_{\{\sigma(a_{j})=r\}}\,\nu_{B}(r\to i% \mid j)$

We now concentrate on the contribution from the good indices $J_{\text{good}}\cap S$ and apply the decomposition lemma (Lemma 17) to the $\nu_{B}$ distributions therein, since they have high entropy.

For $\nu_{B}$ , from the entropy bound $H[F_{B}^{-1}(i)|m_{1},a_{j}]\geq(1-36\varepsilon_{B})\log n$ , we apply Lemma 17 with $A\coloneq 36\varepsilon_{B}\log n$ and $\delta\coloneq\frac{1}{2}$ , giving:

\nu_{B}=\delta\nu_{B}^{(1)}+(1-\delta)\nu_{B}^{(2)},\quad H_{\infty}[\nu_{B}^{% (2)}]\geq\log n-72\varepsilon_{B}\log n-O(1).

Using this decomposition, we can write $Z(i)$ as follows:

Z(i)=Z_{1}(i)+Z_{2}(i),

where

Z_{2}(i):=\frac{1}{2}\sum_{j\in J_{\text{good}}\cap S}\mu_{B}(a_{j})\sum_{r=1}% ^{n}\mathbf{1}_{\{\sigma(a_{j})=r\}}\,\nu_{B}^{(2)}(r\to i\mid j)

and $Z_{1}(i)$ has the remaining terms of $Z(i)$ , and is a non-negative random variable. Intuitively, $Z_{2}(i)$ captures components of the distribution $\nu_{B}$ having high min-entropy.

We now bound the probability of deviation of $Z_{2}(i)$ from its mean. Clearly, for any $\beta$ , $\Pr(Z(i)\leq\beta)\leq\Pr(Z_{2}(i)\leq\beta)$ . We compute the expectation:

	$\displaystyle\operatorname{\mathbb{E}}[Z_{2}(i)]$	$\displaystyle=\frac{1}{2}\sum_{j\in J_{\text{good}}\cap S}\mu_{B}(a_{j})\sum_{% r=1}^{n}\operatorname{\mathbb{E}}[\mathbf{1}_{\{\sigma(a_{j})=r\}}]\,\nu_{B}^{% (2)}(r\to i\mid j)$
		$\displaystyle=\frac{1}{2}\sum_{j\in J_{\text{good}}\cap S}\mu_{B}(a_{j})\sum_{% r=1}^{n}\frac{1}{n}\nu_{B}^{(2)}(r\to i\mid j)\geq\frac{1}{16n}$		(3)

The last step follows from Eq. 2. We now apply a deviation bound due to McDiarmid Theorem 19:

Theorem 25 ([12], [6, The method of averaged bounded differences, Corollary 5.1]).

Let $X_{1},\dots,X_{n}$ be random variables and $f$ a function such that for each $i\in[n]$ there exists $c_{i}\geq 0$ with

\bigl|\mathbb{E}[f\mid X_{1},\dots,X_{i-1},X_{i}=a_{i}]-\mathbb{E}[f\mid X_{1}% ,\dots,X_{i-1},X_{i}=a_{i}^{\prime}]\bigr|\leq c_{i}

for all choices of $a_{i},a_{i}^{\prime}$ . Then, for any $t\geq 0$ ,

\Pr\!\left(|f-\mathbb{E}[f]|\geq t\right)\leq 2\exp\!\left(-\tfrac{2t^{2}}{% \sum_{i=1}^{n}c_{i}^{2}}\right).

We apply the above, for $f$ being $Z_{2}(i)$ and the random variable $X_{j}\equiv\sigma(a_{j})$ . We bound $c:=\sum_{j=1}^{n}c_{j}^{2}$ for $Z_{2}(i)$ : each term in $Z_{2}(i)$ is of the form $\mu_{B}(a_{j})\cdot\nu_{B}^{(2)}(r\to i\mid j)$ , and is non-zero only for one $r=\sigma(a_{j})$ . Thus, each contributes at most:

\max\mu_{B}(a_{j})\cdot\max\nu_{B}^{(2)}(r\to i\mid j)\leq n^{-1+100% \varepsilon_{B}}\cdot n^{-1+72\varepsilon_{B}+o(1)}=n^{-2+172\varepsilon_{B}+o% (1)}.

Each $c_{j}^{2}$ is at most $n^{-4+O(\varepsilon_{B})}$ , and we have at most $n$ terms. This gives us:

c\leq n\cdot n^{-4+O(\varepsilon_{B})}=n^{-3+O(\varepsilon_{B})}.

Applying the concentration bound with $t=\gamma/16n$ , we get:
$\Pr_{\sigma}\left[Z(i)\leq\frac{1-\gamma}{16n}\right]\leq\Pr_{\sigma}\left[Z_{% 2}(i)\leq\frac{1-\gamma}{16n}\right]\leq\exp\left(-\frac{2\gamma^{2}}{256n^{2}% \cdot c}\right)=\exp\!\left(-\frac{1}{128}\,\gamma^{2}\,n^{\,1-O(\varepsilon_{% B})}\right)\$ $\hfill\vartriangleleft$ Setting $b_{1},\ldots b_{r}$ , to be the set of globally good indices $i$ , $\gamma=1/5$ , and a union bound, we conclude the proof of Claim 11. $\hfill\vartriangleleft$

Proof of Claim 12

Proof of Claim 12.

Let Alice’s message $M_{2}$ have $|M_{2}|\leq\varepsilon_{A}n\log n$ . We know that before $M_{2}$ is passed, for every $\sigma$ , since $F_{A,3}$ is independent of $\sigma$ (and $v_{1}$ ) $H\left[F_{A,3}\mid\sigma\right]=n\log n-O(n)$ .

In particular, for $\sigma=\sigma^{*}$ , with probability $\geq 3/4$ over the choice of $M_{2}$ , $H\left[F_{A,3}\mid\sigma^{*},M_{2}=m_{2}\right]\geq(1-4\varepsilon_{A})n\log n$ . Thus, within $R^{\prime}$ on fixing such an $m_{2}$ , we get a sub-rectangle $R^{\prime\prime}$ where, by subadditivity of entropy:

	$\displaystyle\operatorname{\mathbb{E}}_{i\in[n]}[H[F_{A,3}(i)\|R^{\prime\prime}]]$	$\displaystyle\geq(1-4\varepsilon_{A})n\log n$
	$\displaystyle\implies\exists S\subseteq\mathcal{V}_{4}:\|S\|\geq(1-2\sqrt{% \varepsilon_{A}})n\text{ such that}$
	$\displaystyle\forall i\in S:\quad H[F_{A,3}(i)\|R^{\prime\prime}]]$	$\displaystyle\geq(1-2\sqrt{\varepsilon_{A}})\log n$

Call $S$ the uncertain vertices, since Bob cannot predict the next pointer ( $V_{5}$ ) starting at these with reasonable certainty after receiving $M_{2}=m_{2}$ . Intuitively, it is sufficient to show that in $R^{\prime\prime}$ , $V_{4}$ occurs as an uncertain vertex with constant probability. We formalize this next.

Within $R^{\prime\prime}$ , the value of $V_{4}$ is known exactly to Bob: it is the same across $F_{A,3}$ , for any fixed $f_{B}$ . This is because $V_{1}=v_{1},\sigma=\sigma^{*}$ are fixed. Thus, for a fixed $f_{B}$ , if $v_{4}\in S$ , $H[V_{5}]\geq(1-2\sqrt{\varepsilon_{A}})\log n$ . Applying Fano’s inequality (Fact 16.0.1), the probability of Bob making an error in finding the value of $V_{5}$ is at least $P_{e}\geq(1-2\sqrt{\varepsilon_{A}}-\frac{1}{\log n})\geq 0.9$ , for $\varepsilon_{A}$ being small enough.

Since $\sigma^{*}$ satisfies Eq. (1), we get a set $\mathcal{B}=\{b_{1},\ldots,b_{r}\}$ of globally good vertices satisfying Claim 11. Then $|\mathcal{B}\cap S|\geq(1/6-2\sqrt{\varepsilon_{A}})n\geq n/10$ , and each has probability at least $\frac{1}{20n}$ . Thus, the probability of Bob seeing an uncertain vertex as $v_{4}$ in $R^{\prime\prime}$ is at least $1/200$ .

Overall, the probability of error within $R^{\prime}$ is:

\frac{3}{4}\cdot\frac{1}{200}\cdot 0.9\geq\frac{1}{400}

This concludes the proof of Claim 12. $\hfill\vartriangleleft$

Appendix E Missing proofs from Section 5

Proof of Claim 14

Proof of Claim 14.

Let $F:=F_{B,3}$ . Since $|\mathcal{A}_{4}|\geq n/6$ , $H[F\mid R^{\prime}]\geq(1-4\varepsilon_{B})n\log n$ , and $H(V_{4})\leq\log n$ , we obtain

H[F\mid R^{\prime},V_{4}]\geq(1-4\varepsilon_{B})n\log n-\log n\geq(1-5% \varepsilon_{B})n\log n.

There are at least $n/12$ elements in $\mathcal{A}_{4}$ satisfying $\Pr[V_{4}=i]\in(\tfrac{1}{20n},\tfrac{1}{10n})$ ; call this set $\mathcal{D}$ . Let $I[F]\coloneq n\log n-H[F]$ . From the above, $\operatorname{\mathbb{E}}_{v\sim V_{4}}[I[F|R^{\prime},V_{4}=v]]\leq 5% \varepsilon_{B}n\log n$ . Let $c_{1}$ be a large constant to be set later, and $\mathcal{D}_{\text{good}}=\{i\in\mathcal{D}\nobreak\ :\nobreak\ I[F|R^{\prime}% ,V_{4}=i]\leq c_{1}\varepsilon_{B}n\log n\}$ .

Let $\mu$ be the induced distribution on $V_{4}$ in $R^{\prime}$ . We have $\mu(\mathcal{D})\geq 1/240$ . By Markov’s inequality, $\mu(\mathcal{D}_{\text{good}})\geq\mu(\mathcal{D})-\tfrac{5}{c_{1}}\geq\tfrac{% 1}{240}-\tfrac{5}{c_{1}}\geq\tfrac{1}{480}$ , for $c_{1}\coloneq 5\times 480$ .

But this means that we should have at least $\tfrac{1}{480\cdot\tfrac{1}{10n}}=\tfrac{n}{48}=:\alpha_{1}n$ elements in $\mathcal{D}_{\text{good}}$ , since each element has probability at most $1/10n$ . $\hfill\vartriangleleft$

Proof of Claim 16

Proof of Claim 16.

Define $\{Z_{i}\coloneq\mathbbm{1}_{[\mathcal{E}_{i}]}\}_{i\in[r]}$ to be indicator variables for the events $\mathcal{E}_{i}$ under a random choice of $F_{A,3}$ . For any $i$ , we have $\operatorname{\mathbb{E}}[Z_{i}]\geq(1-\gamma)$ . Thus, $\operatorname{\mathbb{E}}[\sum_{i=1}^{r}Z_{i}]\geq(1-\gamma)r$ . Let $\mathcal{E}\equiv\sum_{i}Z_{i}\geq(1-10\gamma)r$ .

Claim 26.

$\Pr\left(\sum_{i=1}^{r}Z_{i}\geq(1-10\gamma)r\right)\geq 1-\exp(-\Omega(\gamma% ^{2}n))$

Proof.

We use McDiarmid’s inequality (see Theorem 19) on the function $f\coloneq\sum_{i\in[r]}Z_{i}$ . The average bounded difference at $i$ satisfy $c_{i}\leq r/(n-r)\leq 2\alpha_{1}$ .

\Pr(Z\leq(1-10\gamma)r)\nobreak\ \leq\nobreak\ \exp\left(-\Omega(81\gamma^{2}(% n-r)^{2})\right)=\exp(-\alpha_{2}\gamma^{2}n)\ldots\textrm{ for some constant % }\alpha_{2}

$\hfill\vartriangleleft$

Let $F\equiv F_{A,3}$ for convenience. Let $Z=(Z_{1},\ldots,Z_{r})$ . Note that $\mathcal{E}\implies|Z|\geq(1-10\gamma)r$ . Since $H[F]\geq n\log n-O(n)$ , we have:

	$\displaystyle H[F\mid M,Z]$	$\displaystyle\geq(1-\varepsilon_{A})n\log n-O(n)$
	$\displaystyle\implies H[F\mid M,Z,\mathcal{E}]$	$\displaystyle\geq\frac{(1-2\varepsilon_{A})n\log n-\Pr(\mathcal{E}^{c})n\log n% }{\Pr(\mathcal{E})}$
	$\displaystyle\implies H[F\mid M,Z,\mathcal{E}]$	$\displaystyle\geq(1-4\varepsilon_{A})n\log n$

Hence, conditioned on $\mathcal{E}$ , with probability at least $3/4$ over choices of $(M,Z)=(m,z)$ , we have that $H[F\mid M=m,Z=z,\mathcal{E}]\geq(1-16\varepsilon_{A})n\log n$ . Fix such a $(m,z)$ pair, and let $z(i_{1})=1,\ldots,z(i_{\ell})=1$ for some $\ell\geq(1-10\gamma)r$ . By subadditivity of entropy:

\displaystyle\operatorname{\mathbb{E}}_{i\in[n]}H[F(i)|M=m,Z=z,\mathcal{E}]

\displaystyle\geq(1-16\varepsilon_{A})\log n

By Markov’s inequality, there are at least $(1-4\sqrt{\varepsilon_{A}})n$ indices $i$ where $H[F(i)|M=m,Z=z,\mathcal{E}]\geq(1-4\sqrt{\varepsilon_{A}})\log n$ . From these, at least $(\alpha_{1}-4\sqrt{\varepsilon_{A}})n$ coordinates have to be from $\mathcal{A}_{4}^{\prime}$ . For each of these, we have that $H[F(b_{i})\mid M=m,\mathcal{E}_{i}]\geq(1-4\sqrt{\varepsilon_{A}})\log n$ . Let $\alpha_{2}\coloneq\alpha_{1}-4\sqrt{\varepsilon_{A}}$ .

Thus, the probability (over $M, Z$ , under the distribution of $F_{A}$ ) that we get at least $\alpha_{2}n$ indices from $\mathcal{A}$ , such that $H[F_{A,3}(b_{i})|M=m,Z=z,\mathcal{E}_{i}]\geq(1-4\sqrt{\varepsilon_{A}})\log n$ is at least:

\Pr[\mathcal{E}]\cdot\frac{3}{4}\geq 1/8\

$\hfill\vartriangleleft$

Appendix F Upper bounds

We adapt the protocols from [5, 15] to infer what depth of pointer can be chased with $O(n\log\log n)$ bits. For simplicity of notation, while describing protocols, we let $f_{A,i}\equiv f_{A,j}$ and $f_{B,i}\equiv f_{B,j}$ all $i, j$ . We will incur a multiplicative factor of $k$ in the communication cost if the functions are different.

Theorem 27.

Let $k^{\prime}\geq\left\lceil\frac{k+5}{3}\right\rceil$ . Then $C^{B,k^{\prime}}(\textsf{PC}(n,k))=O(nk\log\log n)$ .

Proof.

Let $n^{\prime}\coloneq\frac{n}{\log n}$ .

$\blacksquare$

Round 1 (Bob $\to$ Alice): Bob sends the last $\log\log n$ bits of $f_{B}(v_{b})$ for every $v_{b}\in V_{B}$ .
$\blacksquare$

Round 2 (Alice $\to$ Bob): Alice sends the last $\log\log n$ bits of $f_{A}(v_{a})$ for every $v_{a}\in V_{A}$ , and also sends $v_{1}=f_{A}(v_{0})$ along with $f_{A}(v)$ for every possible vertex in Bob’s list that $v_{1}$ could point to.
$\blacksquare$

Round 3 (Bob $\to$ Alice): Bob computes $v_{2}=f_{B}(v_{1})$ . From Alice’s message, he knows $v_{3}=f_{A}(v_{2})$ . He then computes $v_{4}=f_{B}(v_{3})$ and sends $v_{4}$ along with $f_{B}(v)$ for every possible vertex in Bob’s list that $v_{4}$ could point to.
$\blacksquare$

Round 4 (Alice $\to$ Bob): Alice computes $v_{5}=f_{A}(v_{4})$ . From Bob’s message, she knows $v_{6}=f_{B}(v_{5})$ . She then computes $v_{7}=f_{A}(v_{6})$ and sends $v_{7}$ along with $f_{A}(v)$ for every possible vertex in Bob’s list that $v_{7}$ could point to.
$\blacksquare$

…
$\blacksquare$

Round $i$ : If $i$ is even, Alice computes $v_{3i-7}=f_{A}(v_{3i-8})$ , knows the possibilities for $v_{3i-6}=f_{B}(v_{3i-7})$ from Bob’s previous message, computes $v_{3i-5}=f_{A}(v_{3i-6})$ , and sends $v_{3i-5}$ along with $f_{A}(v)$ for all $n^{\prime}$ possible vertices;

if $i$ is odd, Bob performs the analogous computation and sends $v_{3i-5}$ along with $f_{B}(v)$ for all $n^{\prime}$ possible vertices.
$\blacksquare$

…
$\blacksquare$

Round $k^{\prime}$ : If $k^{\prime}$ is even, Alice knows $v_{3k^{\prime}-5}$ and sends it to Bob; if $k^{\prime}$ is odd, Bob knows $v_{3k^{\prime}-5}$ and sends it to Alice, where $k^{\prime}\geq\left\lceil\frac{k+5}{3}\right\rceil$ .

Intuitively, Alice knowing the pointer values for one layer ahead from Bob allows her to “jump” forward $3$ pointers per round: two from her layers and one from Bob.

Rounds 1 and 2 together take $O(n\log\log n)$ bits. All other rounds (except the last round) take $O(\log n+\frac{n}{\log n}\cdot\log n)=O(n)$ bits per round. Since the number of rounds $k^{\prime}$ is constant, the total communication is $O(n\log\log n)$ bits. $\hfill\blacktriangleleft$

Theorem 28.

Let $k^{\prime}\geq\left\lceil\frac{k+6}{4}\right\rceil$ . Then $C^{B,k^{\prime}}(\textsf{bPC}(n,k))=O(nk\log\log n)$ .

Proof.

The protocol follows the same communication structure as in the $\textsf{PC}(n,k)$ protocol, with each party in every round (starting from round 2), each party additionally sending the following $n$ bits every round:

$\blacksquare$

Round 1 (Bob $\to$ Alice): Bob sends the last $\log\log n$ bits of $f_{B}(v)$ for every vertex $v$ , which also implicitly communicates the bit vectors $\chi_{1}(v)=parity(f_{B}(v))$ across all vertices.
$\blacksquare$

Round 2 (Alice $\to$ Bob): The bit vector $\chi_{2}(v):=\chi_{1}(f_{A}(v))$ for all $v\in V_{A}$ .
$\blacksquare$

Round 3 (Bob $\to$ Alice): The bit vector $\chi_{3}(v):=\chi_{2}(f_{B}(v))$ for all $v\in V_{B}$ .
$\blacksquare$

Round 4 (Alice $\to$ Bob): The bit vector $\chi_{4}(v):=\chi_{3}(f_{A}(v))$ for all $v\in V_{A}$ .
$\blacksquare$

Round 5 (Bob $\to$ Alice): The bit vector $\chi_{5}(v):=\chi_{4}(f_{B}(v))$ for all $v\in V_{B}$ .
$\blacksquare$

…
$\blacksquare$

Round i: If $i$ is even, Alice sends $\chi_{i}(v)$ for all $v\in V_{A}$ , else Bob sends $\chi_{i}(v)$ for all $v\in V_{B}$ .
$\blacksquare$

…
$\blacksquare$

Round $k^{\prime}$ : If $k^{\prime}$ is even, Alice knows $v_{3k^{\prime}-5}$ from the base $\textsf{PC}(n,k)$ protocol, and she learns $\chi_{k^{\prime}}$ from the extra parity information exchanged from Round 2. Thus, she sends $\chi_{k^{\prime}-\delta}(v_{3k^{\prime}-5})=\mathrm{parity}(v_{4k^{\prime}-6-% \delta})$ to Bob, where $\delta\in\{0,1,2,3\}$ is chosen so that the resulting vertex is exactly $v_{k}$ . If $k^{\prime}$ is odd, Bob analogously computes and sends $\mathrm{parity}(v_{k})$ to Alice.

Rounds 1 and 2 together take $O(n\log\log n)$ bits. All other rounds (except the last round) have $n$ additional bits compared to the $\textsf{PC}(n,k)$ protocol, but since the number of rounds $k^{\prime}$ is constant, we still have the same total communication of $O(n\log\log n)$ bits. $\hfill\blacktriangleleft$

[bib.bib1] [1] Simon Apers, Yuval Efron, Paweł Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, and Danupon Nanongkai. Cut query algorithms with star contraction. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 507–518. IEEE, 2022.

[bib.bib2] [2] Sepehr Assadi. Recent advances in multi-pass graph streaming lower bounds. ACM SIGACT News, 54(3):48–75, 2023. doi:10.1145/3623800.3623808.

[bib.bib3] [3] Sepehr Assadi, Gillat Kol, Raghuvansh R Saxena, and Huacheng Yu. Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 354–364. IEEE, 2020. doi:10.1109/FOCS46700.2020.00041.

[bib.bib4] [4] László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 337–347. IEEE, 1986.

[bib.bib5] [5] Carsten Damm, Stasys Jukna, and Jiří Sgall. Some bounds on multiparty communication complexity of pointer jumping. Computational Complexity, 7(2):109–127, 1998. doi:10.1007/PL00001595.

[bib.bib6] [6] Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.

[bib.bib7] [7] András Hajnal, Wolfgang Maass, and György Turán. On the communication complexity of graph properties. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 186–191, 1988. doi:10.1145/62212.62228.

[bib.bib8] [8] Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf. New bounds on the classical and quantum communication complexity of some graph properties. In 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science, page 148, 2012.

[bib.bib9] [9] Bala Kalyanasundaram and Georg Schintger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545–557, 1992. doi:10.1137/0405044.

[bib.bib10] [10] Eyal Kushilevitz. Communication complexity. In Advances in Computers, volume 44, pages 331–360. Elsevier, 1997. doi:10.1016/S0065-2458(08)60342-3.

[bib.bib11] [11] Xinyu Mao, Guangxu Yang, and Jiapeng Zhang. Gadgetless lifting beats round elimination: Improved lower bounds for pointer chasing. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325 of Leibniz International Proceedings in Informatics (LIPIcs), pages 75:1–75:14, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2025.75.

[bib.bib12] [12] Colin McDiarmid. On the method of bounded differences. Surveys in combinatorics, 141(1):148–188, 1989.

[bib.bib13] [13] Noam Nisan and Avi Widgerson. Rounds in communication complexity revisited. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 419–429, 1991. doi:10.1145/103418.103463.

[bib.bib14] [14] Christos H Papadimitriou and Michael Sipser. Communication complexity. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 196–200, 1982. doi:10.1145/800070.802192.

[bib.bib15] [15] Stephen J Ponzio, Jaikumar Radhakrishnan, and Srinivasan Venkatesh. The communication complexity of pointer chasing. Journal of Computer and System Sciences, 62(2):323–355, 2001. doi:10.1006/JCSS.2000.1731.

[bib.bib16] [16] Anup Rao and Amir Yehudayoff. Communication complexity: and applications. Cambridge University Press, 2020.

[bib.bib17] [17] Ran Raz and Boris Spieker. On the “log rank”-conjecture in communication complexity. Combinatorica, 15(4):567–588, 1995.

[bib.bib18] [18] Alexander A Razborov. On the distributional complexity of disjointness. In International Colloquium on Automata, Languages, and Programming, pages 249–253. Springer, 1990. doi:10.1007/BFB0032036.

[bib.bib19] [19] Xiaoming Sun and David P Woodruff. Tight bounds for graph problems in insertion streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), pages 435–448. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.435.

[bib.bib20] [20] Amir Yehudayoff. Pointer chasing via triangular discrimination. Combinatorics, Probability and Computing, 29(4):485–494, 2020. doi:10.1017/S0963548320000085.

	$\displaystyle\operatorname{\mathbb{E}}_{i\in[n]}[H[F_{A,3}(i)\|R^{\prime\prime}]]$	$\displaystyle\geq(1-4\varepsilon_{A})n\log n$
	$\displaystyle\implies\exists S\subseteq\mathcal{V}_{4}:\|S\|\geq(1-2\sqrt{% \varepsilon_{A}})n\text{ such that}$
	$\displaystyle\forall i\in S:\quad H[F_{A,3}(i)\|R^{\prime\prime}]]$	$\displaystyle\geq(1-2\sqrt{\varepsilon_{A}})\log n$

Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

1.1 Our Results

Theorem 1 (Main Result).

Theorem 2.

Theorem 3.

1.2 Organization of the paper

2 Preliminaries

2.1 Problem Definitions

Definition 4 (Pointer Chasing, full-version).

Definition 5 (Pointer Chasing, bit-version).

Definition 6.

2.2 Notation

2.3 Communication Complexity preliminaries

Rectangles, Subrectangles.

3 Lower bounds on 𝗛𝗮𝗺𝗖𝘆𝗰𝗹𝗲⁢(𝒏)

Theorem 7.

Proof.

Vertex set for 𝑮′~.

Alice’s Edges (based on 𝝈𝑨).

Bob’s Edges (based on 𝝈𝑩).

Claim 8.

Proof of Claim.

Modification.

4 Randomized lower bound for PC⁢(𝒏,𝟓)

Theorem 9 (Theorem 2 restated).

Proof outline.

Proof.

Claim 10 (Round 1).

Proof.

Claim 11 (Main Claim).

Proof.

Claim 12 (Error after Round 2).

Proof.

5 Randomized lower bound for bPC⁢(𝒏,𝟕)

5.1 Proof of main result

Theorem 13.

Proof Outline.

Proof.

Claim 14.

Proof.

Lemma 15 (Composition Lemma).

Proof.

Claim 16.

References

Appendix A Information Theory Preliminaries

Properties of Entropy.

Fact 16.0.1 (Fano’s Inequality).

Appendix B Statements and proofs of lemmas used

Lemma 17.

Proof.

Lemma 18 (Entropy vs. Min-Entropy [15]).

Theorem 19 ((The method of averaged bounded differences),[12], [6, Corollary 5.1]).

Appendix C Missing proofs from Section 3

Proof of Claim 8.

Observation 20.

Appendix D Missing proofs from Section 4

Proof of Claim 10

Proof of Claim 10.

Proof of Claim 11

Proof of Claim 11.

Definition 21.

Claim 22.

Proof.

Claim 23.

Proof.

Claim 24.

Proof.

Theorem 25 ([12], [6, The method of averaged bounded differences, Corollary 5.1]).

Proof of Claim 12

Proof of Claim 12.

3 Lower bounds on $\mathsf{HamCycle}(n)$

Vertex set for $\tilde{G^{\prime}}$ .

Alice’s Edges (based on $\sigma_{A}$ ).

Bob’s Edges (based on $\sigma_{B}$ ).

4 Randomized lower bound for $\textsf{PC}(n,5)$

5 Randomized lower bound for $\textsf{bPC}(n,7)$