  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 $\sigma^1 \in [n]$ and the
second string $X^2 \in \{0,1\}^n$, player 3 has the second index $\sigma^2 \in
[n]$ along with the third string $X^3 \in \{0,1\}^n$, and so on. Player $k+1$
has the last index $\sigma^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 $\Omega(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 $\Omega(n)$ bits are necessary, for any $k$.
  As our main result, we prove the optimal lower bound of $\Omega(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.
