Reminder: This post contains 4282 words
· 13 min read
· by Xianbin
This post is based on [1]. The communication model is as the same as the model in the posts on multiparty communication complexity (1) and (2) and is also very similar to (3) (in this model, only the players on one side know the incident edges. Notice that the referee (blackboard) knows nothing initially).
The whole idea is based on existing framework on [2]. In the following, let us consider the lower bound for approximate matching.
\(\textbf{Theorem 4}\). For \(r=o(\log k)\), any \(r\)-round protocol computing an approximate matching for general graphs that communicates at most \(k\) bits per round, has no better ratio than \(\Omega(k)\) over the \(r\)-round instance \(\mathcal{D}_{\textup{MM}}^r\).
Overview of the Main Idea
- Suppose that there exists a \(r\)-round protocol \(\pi\) that achieves a ratio \(o(k)\).
- We construct a \(0\)-round instance such that no algorithm can achieve ratio better than \(\Omega(k)\).
- We prove that if there exists a \(r\)-round protocol \(\pi\) with ratio \(\alpha^{-1}\), then there exists a \((r-1)\)-round protocol \(\pi_1\) with \((\alpha-C/n_{r-1})^{-1}\) where \(n_{r-1}\) is the number of nodes in the \((r-1)\)-round instance.
- By Step 3, it is easy to see that it will lead to an algorithm in 0-round protocol with \(o(k)\) ratio, contradiction.
0-round Instance
Given \(k\) pairs of nodes (two parts) and we randomly select \(u\) from one part, and \(v\) from another part. Then, we can prove that there exists no algorithm that can achieve ratio better than \(\Omega(k)\) without communication.
Round Elimination
The most challenging question is on step 3. How to prove such a thing?
Let \(O^{\pi_1}_{r-1}\) be the size of the output of the \((r-1)\)-round protocol over the \((r-1)\)-round instance. Let \(O_{r-1}\) be the size of maximum matching for any \(r\)-round instance.
Basically, our goal is to show that
\[\mathbb{E}[O^{\pi_1}_{r-1}] \geq (\alpha-C/n_{r-1})^{-1} \mathbb{E}[O_{r-1}]\]
To achieve the above goal, definitely, we need to build connections between the protocol \(\pi\) and \(\pi_1\) (because we need to introduce the factor of \(\alpha\)).
- Suppose that we can simulate \(\pi\) by \(\pi_1\) with the set of messages \(\textup{M}^{\leq t}\) and random permutation of vertices based on the \((r-1)\)-round instance (since the \(\pi_1\) protocol is based on he \((r-1)\)-round instance). Then, we have (inevitably, we need to introduce several notations. Readers need to refer to the paper to know these information and the construct instance. If readers do not want to look at the details, just to remember that the following operation is to simulate the process of \(\pi\)) the following:
\[\mathbb{E}_{i\in[p_r]} \mathbb{E}_{B_i \sim \mu_i} , \mathbb{E}_{(\textup{M}^{\leq r}, \Sigma\mid B_i)\sim \mu_i}[O^{\pi_1}_{r-1}] \\= \mathbb{E}_{i\in[p_r]} \mathbb{E}_{(\textup{M}^{\leq r}, G, \Sigma)\sim \mu}[O^\pi_{r-1}]\\ =
\mathbb{E}_{(G,\Sigma)\sim \mu}\mathbb{E}_{i\in[p_r]}[O^\pi_{r-1}]\\ \geq
\mathbb{E}[\frac{O^\pi-n_{r-1}\cdot f_r}{p_r}]\\ \geq
\alpha \cdot \mathbb{E}\mathbb{E}[O_{r-1}] - \frac{n_{r-1\cdot f_r}}{p_r}\]
- Now, let us come to a very important observation. For two distributions \(\mu\) and \(\nu\), the expectation of a random variable under two distributions can be formulated as
\[\mathbb{E}_\nu[X] \leq \mathbb{E}_\mu[X] + \lVert \mu- \nu \rVert_{\text{tvd}} \cdot \max_{X'\in \text{Supp(X)}} X'\]
Let \(\Delta(y) = \lVert \mu- \nu \rVert_{\text{tvd}} \cdot \max_{X'\in \text{Supp(X)}} X' = \frac{1}{2}\cdot \sum_{y\in \Omega: y\sim \mu,\nu} \lvert \mu(y) - \nu(y) \rvert \cdot \max_{X'\in \text{Supp(X)}} X'\)
So,
\[\mathbb{E}_{i\in[p_r]}\mathbb{E}_{B_i\sim \nu_i}\mathbb{E}_{(\textup{M}^{\leq r}, \Sigma\mid B_i)\sim \nu_i}[O^{\pi_1}_{r-1}] \geq \\ \mathbb{E}_{i\in[p_r]}\mathbb{E}_{B_i\sim \mu_i}\mathbb{E}_{(\textup{M}^{\leq r}, \Sigma\mid B_i)\sim \mu_i}[O^{\pi_1}_{r-1}] + \mathbb{E}_{i\in[p_r]}\mathbb{E}_{B_i\sim \mu_i}\frac{n_{r-1}}{2}\cdot \Delta(\textup{M}^{\leq r}, \Sigma\mid B_i)\]
As long as we can prove \(\Delta(\textup{M}^{\leq r}, \Sigma\mid B_i)\) is small enough, it is done. To this end, we need to figure a way to make \(\pi_1\) simulates \(\pi\) well.
The strategy is that recursively sample \(\textup{M}^{\leq r}\) as shown in [1].
Some Notes
In 0-round instance, as there is no content in the blackboard, the transcript \(\Pi\) is empty. The referee has no idea, so it can only guess. Even we allow the referee can output some non-existing edges, the size is at most \(k\). There are \(k^2\) possibilities of \((u,v)\), so the approximation ratio is at most \(k\).
Reference
[1]. Assadi, S., Kol, G. and Zhang, Z., 2024. Rounds vs. Communication Tradeoffs for Maximal Independent Sets. SIAM Journal on Computing, pp.FOCS22-20.
[2]. Alon, N., Nisan, N., Raz, R. and Weinstein, O., 2015, October. Welfare maximization with limited interaction. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (pp. 1499-1512). IEEE.