Optimal Communication Complexity of Chained Index
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916265587638272 |
|---|---|
| author | Sundaresan, Janani |
| author_facet | Sundaresan, Janani |
| contents | We study the CHAIN communication problem introduced by Cormode et al. [ICALP 2019]. It is a generalization of the well-studied INDEX problem. For $k\geq 1$, in CHAIN$_{n,k}$, there are $k$ instances of INDEX, all with the same answer. They are shared between $k+1$ players as follows. Player 1 has the first string $X^1 \in \{0,1\}^n$, player 2 has the first index $σ^1 \in [n]$ and the second string $X^2 \in \{0,1\}^n$, player 3 has the second index $σ^2 \in [n]$ along with the third string $X^3 \in \{0,1\}^n$, and so on. Player $k+1$ has the last index $σ^k \in [n]$. The communication is one way from each player to the next, starting from player 1 to player 2, then from player 2 to player 3 and so on. Player $k+1$, after receiving the message from player $k$, has to output a single bit which is the answer to all $k$ instances of INDEX.
It was proved that the CHAIN$_{n,k}$ problem requires $Ω(n/k^2)$ communication by Cormode et al., and they used it to prove streaming lower bounds for approximation of maximum independent sets. Subsequently, it was used by Feldman et al. [STOC 2020] to prove lower bounds for streaming submodular maximization. However, these works do not get optimal bounds on the communication complexity of CHAIN$_{n,k}$, and in fact, it was conjectured by Cormode et al. that $Ω(n)$ bits are necessary, for any $k$.
As our main result, we prove the optimal lower bound of $Ω(n)$ for CHAIN$_{n,k}$. This settles the open conjecture of Cormode et al. in the affirmative. The key technique is to use information theoretic tools to analyze protocols over the Jensen-Shannon divergence measure, as opposed to total variation distance. As a corollary, we get an improved lower bound for approximation of maximum independent set in vertex arrival streams through a reduction from CHAIN directly. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07026 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Communication Complexity of Chained Index Sundaresan, Janani Computational Complexity We study the CHAIN communication problem introduced by Cormode et al. [ICALP 2019]. It is a generalization of the well-studied INDEX problem. For $k\geq 1$, in CHAIN$_{n,k}$, there are $k$ instances of INDEX, all with the same answer. They are shared between $k+1$ players as follows. Player 1 has the first string $X^1 \in \{0,1\}^n$, player 2 has the first index $σ^1 \in [n]$ and the second string $X^2 \in \{0,1\}^n$, player 3 has the second index $σ^2 \in [n]$ along with the third string $X^3 \in \{0,1\}^n$, and so on. Player $k+1$ has the last index $σ^k \in [n]$. The communication is one way from each player to the next, starting from player 1 to player 2, then from player 2 to player 3 and so on. Player $k+1$, after receiving the message from player $k$, has to output a single bit which is the answer to all $k$ instances of INDEX. It was proved that the CHAIN$_{n,k}$ problem requires $Ω(n/k^2)$ communication by Cormode et al., and they used it to prove streaming lower bounds for approximation of maximum independent sets. Subsequently, it was used by Feldman et al. [STOC 2020] to prove lower bounds for streaming submodular maximization. However, these works do not get optimal bounds on the communication complexity of CHAIN$_{n,k}$, and in fact, it was conjectured by Cormode et al. that $Ω(n)$ bits are necessary, for any $k$. As our main result, we prove the optimal lower bound of $Ω(n)$ for CHAIN$_{n,k}$. This settles the open conjecture of Cormode et al. in the affirmative. The key technique is to use information theoretic tools to analyze protocols over the Jensen-Shannon divergence measure, as opposed to total variation distance. As a corollary, we get an improved lower bound for approximation of maximum independent set in vertex arrival streams through a reduction from CHAIN directly. |
| title | Optimal Communication Complexity of Chained Index |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2404.07026 |