Reminder: This post contains 3388 words
· 10 min read
· by Xianbin
I. Movitiation:
Is there any problem for which the \(k\)-round protocol has a big progress compared to the \((k-1)\)-round protocol? What is that problem?
\(\textbf{Initial Definitinon.}\) We restrict the famous Alice and Bob communication model with \(k\) rounds. Each player is given a list of \(n\) pointers, each pointing to a pointer to the list of the other. The task is to follow those pointers from \(v_0 \in \text{Alice}\) to find the \(k\)-th pointer.
\(\textbf{Informal Definitinon}\). There are \(k+1\) layers of vertices: \(L_0,\ldots,L_k\). In the top layer \(L_0\), there is only one vertex \(v_0\), and all the other \(k\) layers have \(n\) vertices. Each node in one layer has exactly one direction to a vertex in the next layer. We let Alice know the edges coming out of even layers and let Bob know the edges coming out of the odd layers of vertices. Then, we can imagine the “pointer chasing”. The goal is to find the \(k\)-th pointer, i.e., the node \(v_{k+1}\) (or both of palyers will know \(v_k\)).
When Alice starts first, it is easy to give a \(k\)-round complexity algorithm with \(k\log n\) bits of communication.
\[\textcolor{blue}{\text{What about } (k-1) \text{ rounds?}}\]
It is much harder! For simplicity, we use \(CC^{A, k}(f)\) to denote the communication cost of any protocol \(f\) in which \(A\) sends the first message using \(k\) rounds. The define of \(CC^{B, k}(f)\) follows similarly.
\(\textbf{Formal Definition}\). Let \(V_A, V_B\) denote two disjoint sets of \(n\) vertices each and \(V = V_A \cup V_B\). Let \(F_A = \{f_A \mid f_A: V_A \to V_B\}\) and \(F_B = \{f_B \mid f_B: V_B \to V_A\}\).
Let \(f(v) = f_A(v), \forall v\in V_A\) and \(f(v) = f_B(v),\forall v \in V_B\). The goal of pointer chasing is to compute \(g_k: F_A \times F_B \to V\) defined by \(F_k(f_A, f_B) = f^{(k)}(v_0)\), where \(f^{(0)}(v) = v\), and \(f^{(k)}(v) = f(f^{(k-1)}(v))\) for \(k>0\).
II. The Upper Bound
\(\textbf{Theorem } 1\). \(CC^{B,k}(g_k) = O(n\log ^{(k-1)}n)\) for all \(k \leq \log ^*n\).
\(\textbf{Proof}\). This theorem says that if Bob first sends the messages, there is an algorithm that can find \(v_k\) within \(k\) rounds using \(O(n\log ^{(k-1)}n)\) bits.
Let us start from the base case \(k=2\). Our goal is to design an algorithm using one round. Bob sends all of his input, all \(n\) vertices mapping (\(f_B(v)\) for each \(v\in V_B\) ) in \(L_1\) to Alice, who holds \(L_0 (v_0)\) and \(L_2\). Then, we can find \(v_2\). When we know \(v_2\), we know \(v_2\to v_3\), i.e., the second pointer. Here, we use \(O(n\log n)\) bits in total.
We can do better for a more general \(k\). Instead of sending the whole vertices mapping, we have the following procedure.
- Bob sends the last \(\log ^{(k-1)}n\) bits fo of the vertices mapping to Alice.
- Alice receives the mapping, i.e., the last \(\log ^{(k-1)}n\) bits of \(f_B(v_1)\), and sends \(v_1 = f_A(v_0)\) and the last \(\log^{(k-2)}n\) bits of vertices mapping, i.e., \(f_A(v)\) for each possible \(v\in V_A\) to which \(v_1\) points, which indicates possible pointers.
- Repeat until the end.
The main idea of the above procedure is to divide \(L_i\) into \(2^{b_{i+1}}\) blocks where \(b_1 = 0\), each of size \(\lceil \frac{n}{2^{b_{i+1}}}\rceil\). For each time, we map blocks to blocks. Finally, the size of the block is one, and we find \(v_k\). Let \(B_i\) denote the block containing the target \(v_i\). Then, it is easy to see that the communication cost is \(b_{i+1}\lvert B_i\rvert\). After calculation, we obtain the upper bound.
III. Lower Bounds
\(\textbf{Simple Version}:\) The \(\Omega(n)\) bound.
\(\color{red} \text{To be continued \ldots}\)
Reference
[1]. Nisan, Noam, and Avi Widgerson. “Rounds in communication complexity revisited.” Proceedings of the twenty-third annual ACM symposium on Theory of computing. 1991.
[2]. Ponzio, Stephen J., Jaikumar Radhakrishnan, and Srinivasan Venkatesh. “The communication complexity of pointer chasing.” Journal of Computer and System Sciences 62.2 (2001): 323-355.