Optimal Communication Complexity of Chained Index

Sundaresan, Janani

doi:10.4230/LIPIcs.ITCS.2025.89

Optimal Communication Complexity of Chained Index

Janani Sundaresan

Cheriton School of Computer Science, University of Waterloo, Canada

Abstract

We study the chain communication problem introduced by Cormode et al. [ICALP 2019]. For $k\geq 1$ , in the $\textnormal{{chain}}_{n,k}$ problem, there are $k$ string and index pairs $(X_{i},\sigma_{i})$ for $i\in[k]$ such that the value at position $\sigma_{i}$ in string $X_{i}$ is the same bit for all $k$ pairs. The input is 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 value at position $\sigma_{i}$ in $X_{i}$ for any $i\in[k]$ . It is a generalization of the well-studied index problem, which is equivalent to $\textnormal{{chain}}_{n,2}$ .

Cormode et al. proved that the $\textnormal{{chain}}_{n,k}$ problem requires $\Omega(n/k^{2})$ communication, and they used it to prove streaming lower bounds for the approximation of maximum independent sets. Subsequently, Feldman et al. [STOC 2020] used it to prove lower bounds for streaming submodular maximization. However, it is not known whether the $\Omega(n/k^{2})$ lower bound used in these works is optimal for the problem, and in fact, it was conjectured by Cormode et al. that $\Omega(n)$ bits are necessary.

We prove the optimal lower bound of $\Omega(n)$ for $\textnormal{{chain}}_{n,k}$ when $k=o(n/\log n)$ as our main result. This settles the open conjecture of Cormode et al., barring the range of $k=\Omega(n/\log n)$ . The main technique is a reduction to a non-standard index problem where the input to the players is such that the answer is biased away from uniform. This biased version of index is analyzed using tools from information theory. As a corollary, we get an improved lower bound for approximation of maximum independent set in vertex arrival streams via a reduction from chain directly.

Keywords and phrases:

communication complexity, index communciation problem

Funding:

Janani Sundaresan: Supported in part by Sepehr Assadi’s Sloan Research Fellowship and startup grant from University of Waterloo.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Communication complexity

Related Version:

Full Version: https://arxiv.org/abs/2404.07026

Acknowledgements:

The author is thankful to Sepehr Assadi for introducing them to the problem and for insightful discussions on the proof. The author would also like to thank Parth Mittal for useful comments, Christian Konrad for introducing them to the Augmented Chain problem, and the anonymous reviewers of ITCS 2025 for helpful comments and suggestions. The author is very grateful to Mi-Ying Huang, Xinyu Mao, Guangxu Yang and Jiapeng Zhang for an illuminating discussion about the problem. They pointed out an important flaw in an earlier version of this work, and the discussion was instrumental for the new proofs in the current version.

DOI:

10.4230/LIPIcs.ITCS.2025.89

Event:

16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Editors:

Raghu Meka

Series and Publisher:

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

1 Introduction

The index problem is one of the foundational problems in communication complexity. For $n\geq 1$ , in the $\textnormal{{index}}_{n}$ problem, there are two players Alice and Bob. Alice has a string $X\in\{0,1\}^{n}$ and Bob has an index $\sigma\in[n]$ , and Bob has to output the value of $X$ at position $\sigma$ . If the communication is one-way from Alice to Bob, it is easy to show that Alice needs to send $\Omega(n)$ bits to get any constant advantage [1, 30]. This problem has been well-studied in multiple settings, and we know tight trade-offs in the two-party communication model for communication complexity [34], information complexity [24], and quantum communication complexity [8, 24].

Among the numerous applications of communication complexity, one that is of interest to us is proving lower bounds for streaming algorithms. index and its variants, in particular, have been quite useful in this context, for example, in [23, 18, 20, 21, 16, 10]. This is by no means an exhaustive list.

In this paper, we study a natural generalization of index, called chained index ( $\textnormal{{chain}}_{n,k}$ for $n,k\geq 1$ ) introduced by [12]. There are $k$ different instances of $\textnormal{{index}}_{n}$ , correlated so that they have the same answer. They are “chained” together, where each player holds the index to the previous instance, and also the string for the next instance.

Definition 1 (Informal).

In $\textnormal{{chain}}_{n,k}$ , there are $k$ instances of $\textnormal{{index}}_{n}$ , all with the same answer. Players 1 and 2 take on the role of Alice and Bob respectively in the first instance, players 2 and 3 take on the role of Alice and Bob respectively for the second instance, and so on, all the way till players $k$ and $k+1$ for the last instance.

Communication is one-way from each player to the next in ascending order. The last player has to output the answer. The communication cost is the total number of bits in all the messages sent by the players. See Figure 1 for an illustration.

Figure 1: An illustration of the

\textnormal{{chain}}_{n,k}

problem with

k

correlated sub-instances of

\textnormal{{index}}_{n}

from Definition 1. The arrows illustrate that the message is from

P_{i}

to

P_{i+1}

for

i\in[k]

.

In [12], a reduction from chain was employed to get a lower bound for approximation of maximum independent sets in vertex arrival streams. Before its introduction, [28] used the problem implicitly to get a lower bound of $(1-1/e)$ in the approximation factor for maximum matching in $\tilde{O}(n)$ space in vertex arrival streams.

The problem has been used by the breakthrough result of [19] to study the multi-party communication complexity of submodular maximization. They proved that any randomized $p$ -party protocol which maximizes a monotone submodular function $f:\{0,1\}^{N}\rightarrow\mathbb{R}$ , subject to a cardinality constraint of at most $p$ and an approximation factor of at least $(1/2+\epsilon)$ , uses $\Omega(N\epsilon/p^{3})$ communication. This also gave a lower bound for streaming submodular maximization. The chain problem was used by [17] also for similar purposes, but subject to stronger matroid constraints. [7] used a reduction from chain to prove lower bounds for interval independent set selection in streams of split intervals.

We do not know tight bounds for the communication complexity of the chain problem, despite finding varied applications of it. There is a trivial protocol of $O(n)$ bits, where any player can send the entire string to the next player who holds the index. Another simple protocol is for each player to send $O(n/k)$ bits randomly sampled from their strings using public randomness, and with constant probability, in at least one of the $k$ instances, we send the special bit to the player holding the index. However, this still takes $\Omega(n)$ total bits of communication.

In [12], they prove a lower bound of $\Omega(n/k^{2})$ for any $k\geq 1$ through a reduction from conservative multi-party pointer jumping problem, introduced by [14]. They state without proof that a stronger lower bound of $\Omega(n/k)$ can be obtained for a restricted range of $k\leq O((n/\log n)^{1/4})$ . They posed the following conjecture on the optimal communication lower bound.

Conjecture 2 ([12]).

Any protocol that solves $\textnormal{{chain}}_{n,k}$ requires $\Omega(n)$ bits of communication.

[19] made some progress on 2 by showing that among all the messages sent by the players, there is at least one message with $\Omega(n/k^{2})$ bits for every $k\geq 1$ . But the original conjecture is still open, and this is the focus of our work.

1.1 Our Results

We settle 2 almost fully by proving the optimal lower bound of $\Omega(n)$ barring the corner case of when $k$ is too large. As far as we know, this corner case is not a focus for existing reductions from $\textnormal{{chain}}_{n,k}$ .

Theorem 3.

For any $n,k\geq 1$ , any protocol for $\textnormal{{chain}}_{n,k}$ with probability of success at least 2/3, requires $\Omega(n-k\log n)$ total bits of communication.

Therefore, as long as $k=o(n/\log n)$ , we get the optimal $\Omega(n)$ lower bound from Theorem 3.

The proof of Theorem 3 can be found in Section 3. We prove the lower bound in the more general blackboard model of communication, instead of private messages between players (see Section 2.1 for details). The main idea is to analyze $\textnormal{{index}}_{n}$ where Alice and Bob already have some prior advantage in guessing the answer. We elaborate on our techniques in Section 1.2.

As a direct corollary of Theorem 3, we get improvements in streaming lower bounds in [12, 19] through reductions from chain immediately. In particular, we get that any algorithm which $\alpha$ -approximates the size of a maximum independent set in vertex arrival streams requires $\Omega(n^{2}/\alpha^{5}-\log n)$ space, while the previous bound was $\Omega(n^{2}/\alpha^{7})$ in [12]. We present the implications of our result in Section 4.

A further generalization of chain, called Augmented Chain was defined in [15]. Here, instances of Augmented Index are chained together instead. Our lower bound of $\Omega(n-k\log n)$ can be extended to Augmented Chain also, and the details are covered in Section 3.4.

1.2 Our Techniques

In this subsection, we give an overview of the challenges in proving the lower bound and a summary of our techniques. We start by going over the prior techniques.

Prior Techniques

We will briefly talk about the technique used in [19] to prove that there is at least one player who sends $\Omega(n/k^{2})$ bits for any $k\geq 1$ . We will argue that these techniques can be extended to proving a lower bound of $\Omega(n/k)$ for the total number of bits, but not all the way to $\Omega(n)$ bits.

The first step in proving a lower bound for $\textnormal{{chain}}_{n,k}$ in [19] is a decorrelation step – the $k$ instances of $\textnormal{{index}}_{n}$ have the same answer, and they remove this correlation with a hybrid argument. These arguments have been used extensively in the literature (see e.g., [26, 3, 27, 6]). Intuitively, any protocol that tries to solve $\textnormal{{chain}}_{n,k}$ may attempt to solve “many” of the instances of $\textnormal{{index}}_{n}$ , albeit each with a “small” advantage over 1/2, in the hope that the “small” advantages may accrue to get a constant probability of success overall (taking advantage of the fact that all the instances of $\textnormal{{index}}_{n}$ have the same answer). The hybrid argument is a way to reduce proving a lower bound on the overall problem, to proving a lower bound for $k$ different $\textnormal{{index}}_{n}$ problems against these low advantages.

Let us assume, for simplicity, that the protocol tries to get an advantage of $\Omega(1/k)$ in each instance of $\textnormal{{index}}_{n}$ , to get a constant total advantage. We can prove that any protocol that gets an advantage of $\Omega(1/k)$ for $\textnormal{{index}}_{n}$ uses $\Omega(n/k^{2})$ bits of communication using basic tools from information theory [9] (this is quite standard, see e.g., [2] for a direct proof), and this is known to be tight. Therefore, for $k$ instances, we get a lower bound of $\Omega(n/k)$ bits in total. Now, we will argue why this is not the optimal lower bound.

On one hand, for $\textnormal{{index}}_{n}$ , it is known that for any $\delta\in(0,1/2)$ , there is a protocol that uses $O(n\delta^{2})$ bits of communication to get a probability of success $1/2+\delta$ . This means that $\textnormal{{index}}_{n}$ can be solved with advantage $\Omega(1/k)$ in $O(n/k^{2})$ bits; in other words, each “hybrid step” of the previous lower bound argument is optimal. So, then, why can we not get a good protocol for $\textnormal{{chain}}_{n,k}$ by running the protocol for $\textnormal{{index}}_{n}$ with $\delta=1/k$ on all $k$ instances? This protocol would have $O(n/k)$ bits of communication in total. The reason is that the $1/k$ small advantages do not add up as we would like them to. To illustrate this, we will briefly talk about the protocol that gets $\delta$ advantage in $O(n\delta^{2})$ bits for $\textnormal{{index}}_{n}$ .

Protocol for $\textnormal{{index}}_{n}$

First, we will sketch a protocol for $\delta=1/\sqrt{n}$ that uses $O(1)$ bits of communication. Let us imagine that the input $X$ is chosen uniformly at random from $\{0,1\}^{n}$ and the index $\sigma$ is chosen uniformly at random from $[n]$ . Then, Alice finds the majority bit from her string $X$ and sends it to Bob. Bob just outputs the bit sent by Alice. We know, from simple anti-concentration bounds on the binomial distribution, that the number of indices with the majority bit in $X$ is at least $n/2+c\sqrt{n}$ with constant probability for some appropriate constant $c$ . The protocol succeeds if Bob holds the index $\sigma$ to a majority bit, and this happens with probability at least $\frac{1}{2}+\frac{c}{\sqrt{n}}$ .

The assumption that the input $X$ is chosen uniformly at random from $\{0,1\}^{n}$ can be removed using public randomness. Alice and Bob collectively sample a random string $A\in\{0,1\}^{n}$ , and Alice changes her input to $X\oplus A$ so that each bit is 0 or 1 with equal probability. Similarly, the assumption that the index $\sigma$ is chosen uniformly at random from $[n]$ can be removed by Alice and Bob sampling a random permutation of $[n]$ . Alice permutes string $X$ according to this permutation, and Bob changes his input to the index that the permutation maps $\sigma$ to. This is termed as the self-reducibility property of index.

We can also extend the protocol to any $\delta$ by partitioning the string $X$ into $n\delta^{2}$ blocks at random using public randomness and sending the majority bit in each block. Bob knows the block that his input index $\sigma$ belongs to as public randomness is used.

Challenges for $\textnormal{{chain}}_{n,k}$

If we use the protocol we described for $\textnormal{{chain}}_{n,k}$ , we are left with $k$ bits from each instance of $\textnormal{{index}}_{n}$ , which may be the correct answer to the problem with probability $1/2+\Theta(1/k)$ , but, the variance of each of these bits is $1/4-\Theta(1/k^{2})$ . We have a protocol for $\textnormal{{chain}}_{n,k}$ , where, out of the $k$ instances of $\textnormal{{index}}_{n}$ , it finds the right answer for $\approx k/2+\Theta(1)$ instances in expectation. However, the standard deviation of the number of right answers is $\approx\sqrt{k}/2$ , which is enough to mask the $\Theta(1)$ improvement over $k/2$ we get in expectation. If we use a hybrid argument over the total variation distance, each of the smaller “hybrid steps” is optimal, whereas the overall lower bound is not optimal. We cannot achieve a lower bound stronger than $\Omega(n/k)$ .

Our Solution

Instead of keeping track of progress in terms of advantage gained in guessing the answer, we directly keep track of the “information” the message reveals about the answer. Formally, this translates to the change in entropy of the answer, after each successive message. Initially, the players have no information about the answer, and it is uniform over $\{0,1\}$ (the entropy is 1). Any protocol with a large enough probability of success must reduce the entropy of the answer by a large factor (see Fano’s inequality in Proposition 6). We prove that after each message, the entropy is reduced only by an additive factor linear in the length of the message, by a reduction to the index problem. This will give us a lower bound on the total length of the messages.

For $\textnormal{{index}}_{n}$ , in any protocol with probability of success at least $\varepsilon$ , the entropy of the answer conditioned on the message is at most $H_{2}(\varepsilon)$ where $H_{2}(x)=x\log(1/x)+(1-x)\log(1/(1-x))$ is the binary entropy function. In the standard version where the initial entropy is 1, the reduction in entropy is $1-H_{2}(\varepsilon)$ , and it is known that the protocol requires $\Omega(n(1-H_{2}(\varepsilon)))$ communication [24]. This is not sufficient for our application due to the following reason: after the message of $\mathcal{P}_{1}$ , when $\mathcal{P}_{2}$ and $\mathcal{P}_{3}$ attempt to solve $\textnormal{{index}}_{n}$ , they already have some prior advantage that the message of $\mathcal{P}_{1}$ gives them. Therefore, we need to analyze $\textnormal{{index}}_{n}$ when the answer is not uniform over $\{0,1\}$ .

Biased Index

We define the biased index problem, parametrized by $\theta\in[-1/2,1/2]$ . Alice and Bob receive input $Y\in\{0,1\}^{n}$ and $\rho\in[n]$ respectively, such that the value at position $\rho$ in $Y$ (denoted by $Y(\rho)$ ) is 1 with probability $1/2+\theta$ and 0 otherwise. Alice sends a message $M$ to Bob and Bob has to output $Y(\rho)$ . The initial entropy of the answer is $H_{2}(1/2+\theta)$ . We prove that entropy of $Y(\rho)$ conditioned on $M$ is smaller by at most $O((\left|{M}\right|+\log n)/n)$ compared to the initial $H_{2}(1/2+\theta)$ , which is our main contribution (see Lemma 12).

We can show that the entropy of input to Alice, i.e. the random string $Y$ , in such a distribution is at least $\Omega(n\cdot H_{2}(1/2+\theta))$ . Hence, after a message of length $s$ from Alice, the entropy of string $Y$ reduces to $\Omega(n\cdot H_{2}(1/2+\theta)-s)$ . For a randomly chosen position in $Y$ after conditioning on the message, the entropy is at least $\approx H_{2}(1/2+\theta)-s/n$ , which gives a lower bound on $s$ .

In the distribution given to Alice and Bob, however, $\rho$ is not chosen uniformly at random, and in fact, is correlated with the distribution of $Y$ . Such versions of index where the distributions of Alice and Bob are correlated have been studied before (see Sparse Indexing in Appendix A of [5] and Section 3.3 of [36]). This correlation is the main issue in analyzing biased index with information theoretic tools.

Adapted from the approach in Appendix A of [5], we restrict the randomness in $Y$ to a fixed set of indices of a carefully chosen size (based on $\theta$ ), and break this correlation. The loss in entropy of $Y$ is not significant enough to hinder us, and the restriction then allows us to use standard information theoretic tools to analyze biased index (see Section 3.3 for more details).

Independent and Concurrent Work

Independently and concurrently of this work, [33] made progress on 2. They showed a lower bound of $\Omega(n/k+\sqrt{n})$ for oblivious protocols (where the length of the message sent by each player does not depend on the input), and a lower bound of $\Omega(n/k-k)$ for general protocols. We show a lower bound of $\Omega(n-k\log n)$ for all protocols.¹¹1The authors of [33] pointed out an important flaw in the arguments of an earlier version of this work which was posted at around the same time as [33]. This flaw was subsequently fixed in the current version using a global change to the original argument, which now recovers optimal result for $k=o(n/\log n)$ .

Quantitatively, our lower bounds are a factor of almost $k$ stronger, and are optimal for $k=o(n/\log n)$ ; moreover, our lower bound also holds for the Augmented Chain problem of [15]. In terms of techniques, however, the two works are entirely disjoint: their proof is based on a new method of analysis through min-entropy and we use information theoretic approaches.

2 Preliminaries

In this section, we will present the required notation and definitions for our proof.

Notation

For any tuple $A=(A_{1},A_{2},\ldots,A_{m})$ of $m$ items, we use $A_{<i}$ to denote the tuple $(A_{1},A_{2},\ldots,A_{i-1})$ for all $i\in[m]$ . We use sans-serif font to denote random variables. For any random variable ${\mathsf{A}}$ , we use $A\sim{\mathsf{A}}$ to denote any $A$ sampled from the distribution of the random variable ${\mathsf{A}}$ .

For any string $X\in\{0,1\}^{n}$ , we use $X(\sigma)$ to denote the bit at position $\sigma$ in $X$ for $\sigma\in[n]$ . We use $X(<\sigma)$ to denote the string of $\sigma-1$ bits preceding $X(\sigma)$ in $X$ . We use $X(S)$ for any $S\subseteq[n]$ to denote the bits at positions in set $S$ .

For any $x\in[0,1]$ , we use $H_{2}:[0,1]\rightarrow[0,1]$ to denote the binary entropy function.

H_{2}(x)=-x\log x-(1-x)\log(1-x).

We need the following standard approximation of binomial coefficients (see Lemma 7 of Chapter 10 in [32]).

Fact 3 (c.f. [32]).

For any $p\geq 1$ and any $q\in[p-1]$ , we have,

2^{p\cdot H_{2}(q/p)}\cdot\sqrt{\frac{n}{8\pi q(p-q)}}\leq\binom{p}{q}\leq 2^{% p\cdot H_{2}(q/p)}\cdot\sqrt{\frac{n}{2\pi q(p-q)}}

2.1 Communication Complexity Model

We use the standard number-in-hand multi-party model of communication. Only the basic definitions are given in this subsection. More details can be found in textbooks on communication complexity [35, 31].

For any $k\geq 1$ , let $f$ be a function from $\mathcal{A}_{1}\times\mathcal{A}_{2}\times\ldots\times\mathcal{A}_{k}$ to $\{0,1\}$ . There are $k$ players $\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{k}$ where $\mathcal{P}_{i}$ gets an input $a_{i}\in\mathcal{A}_{i}$ for $i\in[k]$ . There is a shared blackboard visible to all the players. The players have access to a shared tape of random bits, along with their own private randomness. In any protocol $\pi$ for $f$ , the players send a message to the blackboard in increasing order ( $\mathcal{P}_{1}$ sends a message followed by $\mathcal{P}_{2}$ , and so on till $\mathcal{P}_{k}$ ). The last player $\mathcal{P}_{k}$ , after all the messages are sent, outputs a single bit denoted by $\pi(a_{1},a_{2},\ldots,a_{k})$ . Protocol $\pi$ is said to solve $f$ with probability of success at least $1-\delta$ if, for all $i\in[k]$ , for any choice of $a_{i}\in\mathcal{A}_{i}$ , we have,

\operatorname*{\textnormal{Pr}}[\pi(a_{1},a_{2},\ldots,a_{k})\neq f(a_{1},a_{2% },\ldots,a_{k})]\leq\delta.

The communication cost of a protocol $\pi$ is defined as the worst case total communication of all the players on the blackboard at the end of the protocol.

Definition 4.

The randomized communication complexity of $f$ , with probability of error $\delta$ , is defined as the minimum communication cost of any protocol which solves $f$ with probability of success at least $1-\delta$ .

2.2 Information Theoretic Tools

Our proof relies on tools from information theory, and we state the basic definitions and the inequalities we need in this section. Proofs of the statements and more details can be found in Chapter 2 of a textbook on information theory by Cover and Thomas [13].

Definition 5 (Shannon Entropy).

For any random variable ${\mathsf{X}}$ over support $\mathcal{A}$ , the Shannon entropy of ${\mathsf{X}}$ , denoted by $\mathbb{H}({\mathsf{X}})$ is defined as,

\mathbb{H}({\mathsf{X}})=\sum_{A\in\mathcal{A}}\operatorname*{\textnormal{Pr}}% [{\mathsf{X}}=A]\cdot\log(1/\operatorname*{\textnormal{Pr}}[{\mathsf{X}}=A]).

For any event $\mathcal{E}$ we define $\mathbb{H}({\mathsf{X}}\mid\mathcal{E})$ in the same way, as the entropy of distribution of ${\mathsf{X}}$ conditioned on the event $\mathcal{E}$ . For any two random variables ${\mathsf{X}}$ and ${\mathsf{Y}}$ , the entropy of ${\mathsf{X}}$ conditioned on ${\mathsf{Y}}$ , denoted by $\mathbb{H}({\mathsf{X}}\mid{\mathsf{Y}})$ is defined as,

\mathbb{H}({\mathsf{X}}\mid{\mathsf{Y}})=\operatorname*{{\mathbb{E}}}_{Y\sim{% \mathsf{Y}}}\mathbb{H}({\mathsf{X}}\mid{\mathsf{Y}}=Y).

Fact 5.

We know the following about entropy and mutual information:

1.

For any random variable ${\mathsf{X}}$ , the entropy obeys the bound: $0\leq\mathbb{H}({\mathsf{X}})\leq\log_{2}(\left|{\mathcal{X}}\right|)$ where $\mathcal{X}$ is the support of ${\mathsf{X}}$ .
2.

For any two random variables ${\mathsf{X}},{\mathsf{Y}}$ , $\mathbb{H}({\mathsf{X}}\mid{\mathsf{Y}})\leq\mathbb{H}({\mathsf{X}})$ with equality holding iff ${\mathsf{X}}\perp{\mathsf{Y}}$ .
3.

Chain Rule of Entropy: For $m\geq 1$ and any tuple of random variables ${\mathsf{X}}=({\mathsf{X}}_{1},{\mathsf{X}}_{2},\ldots,{\mathsf{X}}_{m})$ , $\mathbb{H}({\mathsf{X}})=\sum_{i\in[m]}\mathbb{H}({\mathsf{X}}_{i}\mid{\mathsf% {X}}_{<i})$ .
4.

Subadditivity of entropy: For $m\geq 1$ and any tuple of random variables ${\mathsf{X}}=({\mathsf{X}}_{1},{\mathsf{X}}_{2},\ldots,{\mathsf{X}}_{m})$ , $\mathbb{H}({\mathsf{X}})\leq\sum_{i\in[m]}\mathbb{H}({\mathsf{X}}_{i})$ .

We also need the following proposition, which relates entropy to the probability of correctness while estimating a random variable.

Proposition 6 (Fano’s inequality).

Given a binary random variable ${\mathsf{X}}$ and an estimator random variable $Y$ and a function $g$ such that $g(Y)=X$ with probability at least $1-\delta$ for $\delta<1/2$ ,

\mathbb{H}({\mathsf{X}}\mid{\mathsf{Y}})\leq H_{2}(\delta).

This concludes our preliminaries section.

3 The Lower Bound

In this section, we will prove our lower bound of $\Omega(n)$ on the communication complexity of the $\textnormal{{chain}}_{n,k}$ problem for $k=o(n/\log n)$ . Let us formally define the $\textnormal{{chain}}_{n,k}$ communication problem first.

Definition 7.

The $\textnormal{{chain}}_{n,k}$ communication problem is defined as follows. Given $k+1$ players $\mathcal{P}_{i}$ for $i\in[k+1]$ where,

$\blacksquare$

$\mathcal{P}_{i}$ has a string $X_{i}\in\left\{0,1\right\}^{n}$ for each $i\in[k]$ , and,
$\blacksquare$

$\mathcal{P}_{i}$ for $1<i\leq k+1$ has an index $\sigma_{i-1}\in[n]$ ,

such that,

X_{i}(\sigma_{i})=z,

for some bit $z\in\left\{0,1\right\}$ . The players have a blackboard visible to all the parties. For $i\in[k]$ in ascending order, $\mathcal{P}_{i}$ sends a single message $M_{i}$ , after which the index $\sigma_{i}$ is revealed to the blackboard at no cost. $\mathcal{P}_{k+1}$ has to output whether $z$ is 0 or 1. Refer to Figure 2 for an illustration.

Figure 2: An illustration of the

\textnormal{{chain}}_{n,k}

problem from Definition 7. The solid arrows illustrate that player

\mathcal{P}_{i}

writes a message

M_{i}

to the board. The dashed arrows indicate that

\mathcal{P}_{i}

can read the contents of the board. It also shows the order in which the messages are sent by the players and indices are released.

Let us recall the statement of our main result.

Theorem 3 (restated).

For any $n,k\geq 1$ , any protocol for $\textnormal{{chain}}_{n,k}$ with probability of success at least 2/3, requires $\Omega(n-k\log n)$ total bits of communication.

We give our hard distribution for $\textnormal{{chain}}_{n,k}$ in Section 3.1 and give the proof of Theorem 3 in Section 3.2 except for the analysis of biased index, which is given in Section 3.3. Lastly, we extend the arguments to Augmented Chain in Section 3.4.

3.1 Setting Up the Problem

In this subsection, we start by defining the notation for our proof, and we describe the input distributions to $\textnormal{{chain}}_{n,k}$ .

The input hard distribution is as follows. Let $\mathcal{L}\subset\{0,1\}^{n}$ be the subset of strings where the number of ones is exactly equal to $n/2$ .

Distribution $\mathcal{D}$ for $\textnormal{{chain}}_{n,k}$ :

1.

Pick a bit $z$ uniformly at random from $\left\{0,1\right\}$ .
2.

For each $i\in[k]$ , sample $(X_{i},\sigma_{i})$ uniformly at random from $\mathcal{L}\times[n]$ and independently conditioned on $X_{i}(\sigma_{i})=z$ .

Notation

We use ${\mathsf{X}}_{i}$ to denote the random variable corresponding to string $X_{i}$ and $\bm{\sigma}_{i}$ to denote the random variable corresponding to index $\sigma_{i}$ for $i\in[k]$ . To denote the random variable corresponding to the first $i-1$ strings and indices, we use ${\mathsf{X}}_{<i}$ and $\bm{\sigma}_{<i}$ respectively.

We use ${\mathsf{M}}_{i}$ to denote the random variable corresponding to the message $M_{i}$ sent by $\mathcal{P}_{i}$ to the blackboard. We use $M=(M_{1},M_{2},\ldots,M_{k})$ to denote the tuple containing the messages of all the players, and ${\mathsf{M}}$ to denote the random variable corresponding to $M$ .

Let $\pi$ be a deterministic protocol for $\textnormal{{chain}}_{n,k}$ with probability of success at least $2/3$ when the input is distributed according to $\mathcal{D}$ . We use $\Gamma$ to denote the random variable corresponding to the contents of the blackboard (referred to as a transcript), and we use $\gamma$ to also denote transcripts sampled from $\Gamma$ . We use $\Gamma_{i}$ to denote the random variable of the tuple $(M^{i},\sigma^{i})$ for $i\in[k]$ . We use $\pi(\gamma_{<i},X_{i})$ to denote the output of $\mathcal{P}_{i}$ when the contents of the blackboard are $\gamma_{<i}$ and the input is $X_{i}$ for $i\in[k]$ .

Let $s$ be the total length of all the messages sent by the players in $\gamma$ . We assume that the total length of the messages is exactly $s$ by padding. For any random variable ${\mathsf{A}}$ , we use $\mathcal{D}({\mathsf{A}})$ to denote the distribution of the random variable ${\mathsf{A}}$ , as the input is distributed according to $\mathcal{D}$ . We replace $\mathcal{D}({\mathsf{A}}\mid{\mathsf{B}}=b)$ with $\mathcal{D}({\mathsf{A}}\mid b)$ for ease of readability whenever it is clear from context.

Let ${\mathsf{Z}}$ denote the random variable corresponding to bit $z$ . The bit $z$ corresponds to the answer to $\textnormal{{chain}}_{n,k}$ . We show the lower bound of $\Omega(n-k\log n)$ for distinguishing between the case when $z=0$ and $z=1$ based on the contents of the blackboard.

We need one important observation about the distribution $\mathcal{D}$ .

Observation 8.

For any $i\in[k]$ , random variable ${\mathsf{X}}_{i},\bm{\sigma}_{i}$ is independent of $\Gamma_{<i}$ conditioned on ${\mathsf{Z}}$ .

Proof.

For any fixed value of ${\mathsf{Z}}$ , ${\mathsf{X}}_{i},\bm{\sigma}_{i}$ are chosen uniformly at random from $\mathcal{L}\times[n]$ such that ${\mathsf{X}}_{i}(\bm{\sigma}_{i})={\mathsf{Z}}$ . This choice is independent of any ${\mathsf{X}}_{j},\bm{\sigma}_{j}$ with $j\neq i$ , and thus independent of $\Gamma_{<i}$ . $\hfill\blacktriangleleft$

We are ready to proceed with the proof of our main theorem.

3.2 Proof of Lower Bound

We start by showing that in any successful protocol, the entropy of the distribution of ${\mathsf{Z}}$ conditioned on the message must be small.

Claim 9 (The transcript reveals information about ${\mathsf{Z}}$ .).

\mathbb{H}({\mathsf{Z}}\mid\Gamma)\leq 24/25.

Proof.

We know that $\mathcal{P}_{k+1}$ successfully finds the value of $z$ with probability of success at least 2/3 using the transcript. Thus, using Fano’s inequality in Proposition 6, we have,

\mathbb{H}({\mathsf{Z}}\mid\Gamma)\leq H_{2}(2/3)\leq 24/25.\

$\hfill\vartriangleleft$

The main part of the proof is that we show a lower bound the entropy of ${\mathsf{Z}}$ conditioned on the transcripts using the entropy of the message.

Lemma 10.

For any protocol $\pi$ ,

1-\frac{12}{n}\cdot(\mathbb{H}({\mathsf{M}})+k\log n)\leq\mathbb{H}({\mathsf{Z% }}\mid\Gamma).

Before we prove Lemma 10, we can easily show that it implies Theorem 3.

Proof of Theorem 3.

Combining Lemma 10 with Claim 9, we get,

1-\frac{12}{n}\cdot(\mathbb{H}({\mathsf{M}})+k\log n)\leq\mathbb{H}({\mathsf{Z% }}\mid\Gamma)\leq\frac{24}{25}.

This gives that,

\mathbb{H}({\mathsf{M}})\geq\frac{n}{25\cdot 12}-k\log n.

We know from Section 2.2-(1) that $\mathbb{H}({\mathsf{M}})\leq\log(2^{s})=s$ , which proves that the total number of bits $s=\Omega(n-k\log n)$ for any deterministic protocol. By Yao’s minimax principle, we get a lower bound of $\Omega(n-k\log n)$ on the randomized communication complexity of $\textnormal{{chain}}_{n,k}$ . $\hfill\blacktriangleleft$

The proof of Lemma 10 employs a reduction to the two player $\textnormal{{index}}_{n}$ . However, in these instances of $\textnormal{{index}}_{n}$ , Alice and Bob already have some partial information about the answer. We call this problem the biased index problem, and it is defined based on parameter $\theta\in[-1/2,1/2]$ , which is the initial bias known about the answer.

Definition 11.

The biased index distributional communication problem, denoted by $\textnormal{{bias-ind}}(\theta)$ for $\theta\in[-1/2,1/2]$ , is defined as follows.

Sample $W\in\{0,1\}$ such that $W=1$ with probability $1/2+\theta$ , and $W=0$ otherwise. Sample $(Y,\rho)$ uniformly at random from $\mathcal{L}\times[n]$ conditioned on $Y(\rho)=W$ . Give string $Y$ to Alice, and index $\rho$ to Bob. Bob has to output $Y(\rho)$ after a single message $M_{\textsc{index}}$ from Alice.

Let $\pi_{\textsc{index}}$ be a deterministic protocol for $\textnormal{{bias-ind}}(\theta)$ . Let ${\mathsf{W}},{\mathsf{Y}},\bm{\rho},{\mathsf{M}}_{\textsc{index}}$ denote the random variables corresponding to $W, Y$ , $\rho$ and $M_{\textsc{index}}$ respectively. Let $\mathcal{D}_{\theta}$ denote the joint distribution of ${\mathsf{W}},{\mathsf{Y}},\bm{\rho}$ and ${\mathsf{M}}_{\textsc{index}}$ in $\textnormal{{bias-ind}}(\theta)$ .

We prove the following lemma about $\textnormal{{bias-ind}}(\theta)$ in Section 3.3.

Lemma 12 (Biased Index).

For any protocol $\pi_{\textsc{index}}$ for $\textnormal{{bias-ind}}(\theta)$ ,

\mathbb{H}({\mathsf{W}}\mid{\mathsf{M}}_{\textsc{index}},\bm{\rho})\geq H_{2}(% 1/2+\theta)-\frac{2}{n}\cdot(\mathbb{H}({\mathsf{M}}_{\textsc{index}})+\log n).

We can prove Lemma 10 using Lemma 12, but the proof is deferred to the full version.

3.3 Biased Index

In this subsection, we will prove Lemma 12. Let us first recall the input distribution to $\textnormal{{bias-ind}}(\theta)$ .

Distribution $\mathcal{D}_{\theta}$ : Sample $W=1$ with probability $1/2+\theta$ and set $W=0$ otherwise. Sample $(Y,\rho)\in\mathcal{L}\times[n]$ conditioned on $Y(\rho)=W$ .

In $\mathcal{D}_{\theta}$ , the distribution of ${\mathsf{Y}}$ and $\bm{\rho}$ are highly correlated. We give an alternate way of sampling $Y,\rho$ so that this correlation is removed partially.

Distribution $\mathcal{D}_{\theta}^{\prime}$ :

For $\theta\geq 0$ :

1.

Sample set $T\subset[n]$ of size $b=n/(1+2\theta)$ uniformly at random.
2.

Sample a set $S$ of $n/2$ indices from $T$ uniformly at random and set them to 1, and set $[n]\setminus S$ to 0 to get $Y$ .
3.

Sample $\rho$ by sampling an index uniformly at random from $T$ .

For $\theta<0$ :

1.

Sample set $T\subset[n]$ of size $b=n/(1-2\theta)$ uniformly at random.
2.

Sample a set $S$ of $n/2$ indices from $T$ uniformly at random and set them to 0, and set $[n]\setminus S$ to 1 to get $Y$ .
3.

Sample $\rho$ by sampling an index uniformly at random from $T$ .

In this section, we assume that $\theta\geq 0$ . For the case when $\theta<0$ , the proof follows in the same vein, and is not presented. Let ${\mathsf{T}},{\mathsf{S}}$ denote the random variables corresponding to set $T$ and set $S$ respectively. We show that distributions $\mathcal{D}_{\theta}$ and $\mathcal{D}_{\theta}^{\prime}$ are in fact identical, and the proofs can be found in the full version.

Claim 13.

In distribution $\mathcal{D}_{\theta}$ , for any $(Y,\rho)\in\mathcal{L}\times[n]$ ,

\operatorname*{\textnormal{Pr}}({\mathsf{Y}}=Y,\bm{\rho}=\rho)=\begin{cases}% \frac{1+2\theta}{n\cdot\binom{n}{n/2}}&\textnormal{when $Y(\rho)=1$},\\ \frac{1-2\theta}{n\cdot\binom{n}{n/2}}&\textnormal{when $Y(\rho)=0$.}\end{cases}

Claim 14.

Distribution $\mathcal{D}_{\theta}$ is the same as $\mathcal{D}_{\theta}^{\prime}$ .

Using this alternate way of sampling, it is easy to see that random variables ${\mathsf{Y}}$ and $\bm{\rho}$ are independent of each other conditioned on ${\mathsf{T}}$ . It can also be extended to include random variable ${\mathsf{M}}_{\textsc{index}}$ , as it is only a function of ${\mathsf{Y}}$ .

Observation 15.

In distribution $\mathcal{D}_{\theta}^{\prime}$ , conditioned on ${\mathsf{T}}=T$ , for any $i\in T$ , distribution of random variables ${\mathsf{Y}},{\mathsf{M}}_{\textsc{index}}$ is independent of event $\bm{\rho}=i$ .

Proof.

Conditioned on ${\mathsf{T}}=T$ , string $Y$ is chosen by picking an $n/2$ size set $S$ uniformly at random from $T$ , and setting these indices to 1, and this choice also fixes ${\mathsf{M}}_{\textsc{index}}$ as the protocol is deterministic. And index $\rho$ is chosen uniformly at random from $T$ , independently of the choice of $S$ , by definition of $\mathcal{D}_{\theta}^{\prime}$ . Thus, choice of $\bm{\rho}=i$ is independent of random variables ${\mathsf{Y}},{\mathsf{M}}_{\textsc{index}}$ . $\hfill\blacktriangleleft$

Next, we will show that even conditioned on ${\mathsf{T}}$ , the entropy of ${\mathsf{Y}}$ remains large.

Claim 16.

\mathbb{H}({\mathsf{Y}}\mid{\mathsf{T}})\geq\frac{n}{(1+2\theta)}\cdot H_{2}(1% /2+\theta)-2\log n.

Proof.

We assume that $\theta<1/2$ , as otherwise, the statement is vacuously true. $H_{2}(1)=0$ by definition, and entropy is always non-negative by Section 2.2-(1).

Conditioned on ${\mathsf{T}}=T$ , we know that ${\mathsf{Y}}$ is fixed by choosing set ${\mathsf{S}}$ uniformly at random. Thus,

$\displaystyle\mathbb{H}({\mathsf{Y}}\mid{\mathsf{T}})$	$\displaystyle=\log\left(\binom{b}{n/2}\right)$	(by Section 2.2-(1))
	$\displaystyle\geq\log\left(2^{bH_{2}(n/2b)}\cdot\sqrt{\frac{b}{8(n/2)(b-n/2)}}\right)$	(by Section 2, and $n/2<b$ , as $\theta<1/2$ )
	$\displaystyle=b\cdot H_{2}(n/2b)+\frac{1}{2}\cdot\log(\frac{b}{8(n/2)(b-n/2)})$
	$\displaystyle=\frac{n}{(1+2\theta)}\cdot H_{2}(1/2+\theta)+\frac{1}{2}\log(% \frac{1}{4n\cdot(1/2-\theta)})$
	$\displaystyle\geq\frac{n}{(1+2\theta)}\cdot H_{2}(1/2+\theta)+\frac{1}{2}\log(% 1/4n)$	(as $1/2-\theta\leq 1$ )
	$\displaystyle\geq\frac{n}{(1+2\theta)}\cdot H_{2}(1/2+\theta)-2\log n.$

$\hfill\vartriangleleft$

We are ready to prove Lemma 12.

Proof of Lemma 12.

We can lower bound the entropy of ${\mathsf{W}}$ conditioned on ${\mathsf{M}}_{\textsc{index}},\bm{\rho}$ as,

$\displaystyle\mathbb{H}({\mathsf{W}}\mid{\mathsf{M}}_{\textsc{index}},\bm{\rho})$	$\displaystyle\geq\mathbb{H}({\mathsf{W}}\mid{\mathsf{M}}_{\textsc{index}},\bm{% \rho},{\mathsf{T}})$	(as conditioning reduces entropy, Section 2.2-(2))
	$\displaystyle=\operatorname*{{\mathbb{E}}}_{{\mathsf{T}}=T}\big{[}\frac{1}{b}% \cdot\sum_{\rho\in T}\mathbb{H}({\mathsf{W}}\mid{\mathsf{M}}_{\textsc{index}},% \bm{\rho}=\rho,{\mathsf{T}}=T)\big{]}$	(as $\bm{\rho}$ is uniform over $T$ )
	$\displaystyle=\operatorname*{{\mathbb{E}}}_{{\mathsf{T}}=T}\big{[}\frac{1}{b}% \cdot\sum_{\rho\in T}\mathbb{H}({\mathsf{Y}}(\rho)\mid{\mathsf{M}}_{\textsc{% index}},\bm{\rho}=\rho,{\mathsf{T}}=T)\big{]}$	(as $W=Y(\rho)$ by definition of $\mathcal{D}_{\theta}$ )
	$\displaystyle=\operatorname*{{\mathbb{E}}}_{{\mathsf{T}}=T}\big{[}\frac{1}{b}% \cdot\sum_{\rho\in T}\mathbb{H}({\mathsf{Y}}(\rho)\mid{\mathsf{M}}_{\textsc{% index}},{\mathsf{T}}=T)\big{]}$	(as ${\mathsf{Y}},{\mathsf{M}}_{\textsc{index}}\perp(\bm{\rho}=\rho)\mid{\mathsf{T}% }=T$ , by 15)
	$\displaystyle\geq\operatorname*{{\mathbb{E}}}_{{\mathsf{T}}=T}\big{[}\frac{1}{% b}\cdot\mathbb{H}({\mathsf{Y}}(T)\mid{\mathsf{M}}_{\textsc{index}},{\mathsf{T}% }=T)\big{]}$	(by subadditivity of entropy, Section 2.2-(4))
	$\displaystyle=\operatorname*{{\mathbb{E}}}_{{\mathsf{T}}=T}\big{[}\frac{1}{b}% \cdot\mathbb{H}({\mathsf{Y}}\mid{\mathsf{M}}_{\textsc{index}},{\mathsf{T}}=T)% \big{]}$	(as $Y([n]\setminus T)$ is fixed to be 0)
	$\displaystyle=\frac{1}{b}\cdot\mathbb{H}({\mathsf{Y}}\mid{\mathsf{M}}_{\textsc% {index}},{\mathsf{T}}).$

Thus it follows that,

\mathbb{H}({\mathsf{Y}}\mid{\mathsf{M}}_{\textsc{index}},{\mathsf{T}})\leq b% \cdot\mathbb{H}({\mathsf{W}}\mid{\mathsf{M}}_{\textsc{index}},\bm{\rho}).

(1)

We also have,

$\displaystyle\mathbb{H}({\mathsf{Y}}\mid{\mathsf{T}})$	$\displaystyle=\mathbb{H}({\mathsf{Y}},{\mathsf{M}}_{\textsc{index}}\mid{% \mathsf{T}})$	(as $M$ is fixed by $Y$ )
	$\displaystyle=\mathbb{H}({\mathsf{M}}_{\textsc{index}}\mid{\mathsf{T}})+% \mathbb{H}({\mathsf{Y}}\mid{\mathsf{M}}_{\textsc{index}},{\mathsf{T}})$	(by chain rule of entropy, Section 2.2-(3))
	$\displaystyle\leq\mathbb{H}({\mathsf{M}}_{\textsc{index}}\mid{\mathsf{T}})+b% \cdot\mathbb{H}({\mathsf{W}}\mid{\mathsf{M}}_{\textsc{index}},\bm{\rho})$	(by Eq 1)
	$\displaystyle\leq\mathbb{H}({\mathsf{M}}_{\textsc{index}})+b\cdot\mathbb{H}({% \mathsf{W}}\mid{\mathsf{M}}_{\textsc{index}},\bm{\rho}).$	(as conditioning reduces entropy, by Section 2.2-(2))

Combining with Claim 16, we get,

	$\displaystyle\mathbb{H}({\mathsf{M}}_{\textsc{index}})+b\cdot\mathbb{H}({% \mathsf{W}}\mid{\mathsf{M}}_{\textsc{index}},\bm{\rho})$	$\displaystyle\geq b\cdot H_{2}(1/2+\theta)-2\log n$		(as $b=n/(1+2\theta)$ )
	$\displaystyle b\cdot\mathbb{H}({\mathsf{W}}\mid{\mathsf{M}}_{\textsc{index}},% \bm{\rho})$	$\displaystyle\geq b\cdot H_{2}(1/2+\theta)-(\mathbb{H}({\mathsf{M}}_{\textsc{% index}})+2\log n).$		(rearranging the terms)

Dividing both sides by $b$ , we get,

	$\displaystyle\mathbb{H}({\mathsf{W}}\mid{\mathsf{M}}_{\textsc{index}},\bm{\rho})$	$\displaystyle\geq H_{2}(1/2+\theta)-\frac{1}{b}\cdot(\mathbb{H}({\mathsf{M}}_{% \textsc{index}})+2\log n)$
		$\displaystyle\geq H_{2}(1/2+\theta)-\frac{2}{n}\cdot(\mathbb{H}({\mathsf{M}}_{% \textsc{index}})+2\log n),$		(as $b\geq n/2$ )

finishing the proof. $\hfill\blacktriangleleft$

3.4 Extension to Augmented Chain

In this subsection, we will extend our lower bound to the Augmented Chain problem introduced by [15]. We begin by defining Augmented Index.

Augmented Index is a close variant of the index problem. Here, in addition to having the index $\sigma$ , Bob also has the bits $X(<\sigma)$ . We know that this generalization also requires $\Omega(n)$ communication when Alice sends a message to Bob [34]. This problem is particularly useful for proving lower bounds for turnstile streams (see e.g., [11, 25, 16], and references therein). Tight information cost trade-off for this variant in the two-way communication model was proved by [9].

The formal definition of Augmented Chain follows.

Definition 17 (Augmented Chain).

The $\textnormal{{aug-chain}}_{n,k}$ communication problem is defined as follows. Given $k+1$ players $\mathcal{P}_{i}$ for $i\in[k+1]$ where,

$\blacksquare$

$\mathcal{P}_{i}$ has a string $X_{i}\in\left\{0,1\right\}^{n}$ for each $i\in[k]$ ,
$\blacksquare$

$\mathcal{P}_{i}$ for $1<i\leq k+1$ has an index $\sigma_{i-1}\in[n]$ , and a string $X_{i-1}(<\sigma_{i-1})$ ,

such that,

X_{i}(\sigma_{i})=z,

for some bit $z\in\left\{0,1\right\}$ . The players have a blackboard visible to all the parties. For $i\in[k]$ in ascending order, $\mathcal{P}_{i}$ sends a single message $M_{i}$ , after which the index $\sigma_{i}$ , and the string $X_{i-1}(<\sigma_{i-1})$ are revealed to the blackboard at no cost. $\mathcal{P}_{k+1}$ has to output whether $z$ is 0 or 1. Refer to Figure 3 for an illustration.

Figure 3: An illustration of the

\textnormal{{aug-chain}}_{n,k}

problem from Definition 17. The solid arrows illustrate that player

\mathcal{P}_{i}

writes a message

M_{i}

to the board. The dashed arrows indicate that

\mathcal{P}_{i}

can read the contents of the board. The order in which the messages are sent and indices, strings are released is also shown.

For the chained version of Augmented Index, the lower bound that at least one player sends $\Omega(n/k^{2})$ bits holds true, and the proof follows with minimal changes. Using this, [15] proved lower bounds for interval independent set selection in turnstile streams with weighted intervals.

We prove the following result about $\textnormal{{aug-chain}}_{n,k}$ .

Theorem 18.

For any $n,k\geq 1$ , any protocol for $\textnormal{{aug-chain}}_{n,k}$ with probability of success at least 2/3 requires communication $\Omega(n-k\log n)$ .

A proof sketch detailing the changes needed to prove Theorem 18 is given in the full version. Most parts of the proof are similar to the proof of Theorem 3.

4 Applications to Streaming

In this section we give applications of our main result to independent sets in vertex arrival streams and streaming submodular maximization.

4.1 Independent Sets

In edge arrival streams, for any graph $G=(V,E)$ , the vertex set $V$ with $n$ vertices is given, and the edges $E$ arrive in any arbitrary order. We are required to process the graph in limited space.

In vertex arrival streams, for any graph $G=(V,E)$ , the edges are grouped by their incident vertices. Vertices from $V$ arrive one by one (in any arbitrary order), and when a vertex arrives, all the edges connecting it to any previously arrived vertices are revealed. This makes the vertex arrival stream a strictly easier model than the edge arrival stream, as the order of edges is restricted.

Indeed, for the maximal independent set problem, we know that finding algorithms in vertex arrival streams is easier; the greedy algorithm produces a maximal independent set in $\widetilde{O}(n)$ space, whereas, in edge arrival streams, any algorithm which finds a maximal independent set requires $\Omega(n^{2})$ space [4, 12].

Maximum independent set (MIS), however, is provably hard in both vertex arrival streams and edge arrival streams. It is known that, any algorithm which performs an $\alpha$ -approximation of MIS in edge arrival streams requires $\Omega(n^{2}/\alpha^{2})$ space from [22]. In vertex arrival streams, [12] proved a lower bound of $\Omega(n^{2}/\alpha^{7})$ . They also gave the following connection between chain problem and MIS in the proof of Theorem 9 of their paper.

Proposition 19 (Rephrased from [12]).

For any $\alpha\geq 1$ , any algorithm that gives an $\alpha$ -approximation of maximum independent sets in vertex arrival streams for $n$ -vertex graphs using space at most $s$ and probability of success at least 2/3 can be used to solve $\textnormal{{chain}}_{n^{2}/64\alpha^{4},2\alpha}$ with communication at most $2\alpha\cdot s$ bits and success probability at least $2/3$ .

Our lower bound Theorem 3, along with Proposition 19 directly gives the following corollary.

Corollary 20.

For $\alpha\geq 1$ , any $\alpha$ -approximation of maximum independent sets in $n$ -vertex graphs in vertex arrival streams uses $\Omega(n^{2}/\alpha^{5}-\log n)$ space.

This further reduces the gap between the lower bounds for $\alpha$ -approximation of MIS in vertex arrival streams and edge arrival streams by an $\alpha^{2}$ factor.

4.2 Submodular Maximization

In this subsection, we will summarize our slight improvements to lower bounds for streaming submodular maximization.

A function $f$ over ground set $V$ from $f:2^{V}\rightarrow\mathbb{R}$ is submodular if and only if, for any two sets $A\subset B\subset V$ and for any element $x\in V\setminus B$ ,

f(B\cup\{x\})-f(B)\leq f(A\cup\{x\})-f(A).

This captures the diminishing returns property of any submodular function.

We are interested in maximization of a monotone submodular function subject to a cardinality constraint. That is, for a given $\ell$ , we want to find a subset $S\subset V$ with $\left|{S}\right|\leq\ell$ such that for any other set $T\subset V$ with $\left|{T}\right|\leq\ell$ , $f(S)\geq f(T)$ .

We are given oracle access to function $f$ , however, we do not have access to the entirety of the ground set. The elements of the ground set $V$ arrive one by one, and the algorithm has space $s$ to either store the incoming element or to discard it. The algorithm can query the oracle to $f$ with any subset of the elements currently in storage. We want the storage to be roughly the same as the output size, which is $\ell$ .

In this model, [29] gave an algorithm which finds a $(1/2-\epsilon)$ -approximation in $O(\ell/\epsilon)$ space. [19] showed that a better approximation was not possible. They proved that any algorithm which gets a $(1/2+\epsilon)$ -approximation uses $\Omega(\epsilon\left|{V}\right|/\ell^{3})$ . They give the following connection to the chain problem in Theorem 1.3 and Theorem 1.4 of their paper.

Proposition 21 (Rephrased from [19]).

For any $\epsilon>0$ , there exists a constant $\ell_{0}$ such that for any $\ell\geq\ell_{0}$ , any randomized streaming algorithm which maximizes a monotone submodular function $f:2^{V}\rightarrow\mathbb{R}$ subject to cardinality constraint of at most $\ell$ , using space at most $s$ and with approximation factor at least $(1/2+\epsilon)$ in expectation can be used to solve $\textnormal{{chain}}_{\left|{V}\right|/\ell,\ell}$ with probability of success at least 2/3 and communication at most $s\cdot O(\ell/\epsilon)$ .

We get an improvement of $\ell$ factor over the current state-of-art lower bound in [19] as a corollary of Theorem 3.

Corollary 22.

For any $\epsilon>0$ , there exists a constant $\ell_{0}$ such that for any $\ell\geq\ell_{0}$ , any streaming algorithm that maximizes a monotone submodular function $f:2^{V}\rightarrow\mathbb{R}$ subject to a cardinality constraint of at most $\ell$ , with an approximation factor at least $(1/2+\epsilon)$ , requires $\Omega(\left|{V}\right|\epsilon/\ell^{2}-\varepsilon\log(\left|{V}\right|))$ space.

References

[1] Farid Ablayev. Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science, 157(2):139–159, 1996. doi:10.1016/0304-3975(95)00157-3.
[2] S. Assadi. Lecture notes on sublinear algorithms. https://sepehr.assadi.info/courses/cs514-s20/lec8.pdf, 2020.
[3] S. Assadi, G. Kol, R. R. Saxena, and H. 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, Los Alamitos, CA, USA, November 2020. IEEE Computer Society. doi:10.1109/FOCS46700.2020.00041.
[4] Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear algorithms for ( $\Delta$ + 1) vertex coloring. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 767–786, 2019. doi:10.1137/1.9781611975482.48.
[5] Sepehr Assadi, Sanjeev Khanna, and Yang Li. Tight bounds for single-pass streaming complexity of the set cover problem. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 698–711, New York, NY, USA, 2016. Association for Computing Machinery. doi:10.1145/2897518.2897576.
[6] Sepehr Assadi and Janani Sundaresan. (noisy) gap cycle counting strikes back: Random order streaming lower bounds for connected components and beyond. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 183–195, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585192.
[7] Sujoy Bhore, Fabian Klute, and Jelle J. Oostveen. On streaming algorithms for geometric independent set and clique. In Parinya Chalermsook and Bundit Laekhanukit, editors, Approximation and Online Algorithms, pages 211–224, Cham, 2022. Springer International Publishing. doi:10.1007/978-3-031-18367-6_11.
[8] Harry Buhrman and Ronald Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the Annual IEEE Conference on Computational Complexity, pages 120–130, February 2001. doi:10.1109/CCC.2001.933879.
[9] Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, and Andrew McGregor. Information cost tradeoffs for augmented index and streaming language recognition. SIAM Journal on Computing, 42(1):61–83, 2013. doi:10.1137/100816481.
[10] Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs. In International Colloquium on Automata, Languages and Programming, 2021. URL: https://api.semanticscholar.org/CorpusID:232014583.
[11] Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, pages 205–214, New York, NY, USA, 2009. Association for Computing Machinery. doi:10.1145/1536414.1536445.
[12] Graham Cormode, Jacques Dark, and Christian Konrad. Independent Sets in Vertex-Arrival Streams. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1–45:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2019.45.
[13] Thomas M. Cover and Joy A. Thomas. Elements of information theory (2. ed.). Wiley, 2006.
[14] Carsten Damm, Stasys Jukna, and Jirí Sgall. Some bounds on multiparty communication complexity of pointer jumping. In Claude Puech and Rüdiger Reischuk, editors, STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996, Proceedings, volume 1046 of Lecture Notes in Computer Science, pages 643–654. Springer, 1996. doi:10.1007/3-540-60922-9_52.
[15] Jacques Dark, Adithya Diddapur, and Christian Konrad. Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting. In Patricia Bouyer and Srikanth Srinivasan, editors, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023), volume 284 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1–24:17, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.FSTTCS.2023.24.
[16] Jacques Dark and Christian Konrad. Optimal lower bounds for matching and vertex cover in dynamic graph streams. In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 30:1–30:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.CCC.2020.30.
[17] Ashkan Norouzi Fard, Moran Feldman, Ola Svensson, and Rico Zenklusen. Submodular maximization subject to matroid intersection on the fly. In 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, pages 52:1–52:14, 2022. doi:10.4230/LIPICS.ESA.2022.52.
[18] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM J. Comput., 38(5):1709–1727, 2008. doi:10.1137/070683155.
[19] Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. The one-way communication complexity of submodular maximization with applications to streaming and robustness. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 1363–1374, New York, NY, USA, 2020. Association for Computing Machinery. doi:10.1145/3357713.3384286.
[20] Sudipto Guha and Andrew McGregor. Stream order and order statistics: Quantile estimation in random-order streams. SIAM J. Comput., 38(5):2044–2059, 2009. doi:10.1137/07069328X.
[21] Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 287–298, 2013. doi:10.1109/CCC.2013.37.
[22] Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, and Chengu Wang. Streaming and communication complexity of clique approximation. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 449–460. Springer, 2012. doi:10.1007/978-3-642-31594-7_38.
[23] P. Indyk and D. Woodruff. Tight lower bounds for the distinct elements problem. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 283–288, 2003. doi:10.1109/SFCS.2003.1238202.
[24] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A property of quantum relative entropy with an application to privacy in quantum communication. J. ACM, 56(6), September 2009. doi:10.1145/1568318.1568323.
[25] Daniel M. Kane, Jelani Nelson, and David P. Woodruff. On the exact space complexity of sketching and streaming small norms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pages 1161–1178, USA, 2010. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973075.93.
[26] Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating MAX-CUT. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1263–1282. SIAM, 2015. doi:10.1137/1.9781611973730.84.
[27] Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, and Samson Zhou. Noisy Boolean Hidden Matching with Applications. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 91:1–91:19, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2022.91.
[28] Mikhail Kapralov. Better bounds for matchings in the streaming model. In ACM-SIAM Symposium on Discrete Algorithms, 2012. URL: https://api.semanticscholar.org/CorpusID:448251.
[29] Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3311–3320. PMLR, 09–15 June 2019. URL: https://proceedings.mlr.press/v97/kazemi19a.html.
[30] Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’95, pages 596–605, New York, NY, USA, 1995. Association for Computing Machinery. doi:10.1145/225058.225277.
[31] Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997.
[32] F. J. (Florence Jessie) MacWilliams and N. J. A. (Neil James Alexander) Sloane. The theory of error-correcting codes. North-Holland mathematical library ; v. 16. North-Holland Pub. Co., Amsterdam, 1978 - 1977.
[33] Guangxu Yang Mi-Ying Huang, Xinyu Mao and Jiapeng Zhang. Breaking square-root loss barriers via min-entropy. Electron. Colloquium Comput. Complex., pages TR24–067, 2024. URL: https://eccc.weizmann.ac.il/report/2024/067/.
[34] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. Journal of Computer and System Sciences, 57(1):37–49, 1998. doi:10.1006/jcss.1998.1577.
[35] Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. doi:10.1017/9781108671644.
[36] Mert Saglam. Tight bounds for data stream algorithms and communication problems. Master’s thesis, Simon Fraser University, 2011.

[bib.bib1] [1] Farid Ablayev. Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science, 157(2):139–159, 1996. doi:10.1016/0304-3975(95)00157-3.

[bib.bib2] [2] S. Assadi. Lecture notes on sublinear algorithms. https://sepehr.assadi.info/courses/cs514-s20/lec8.pdf, 2020.

[bib.bib3] [3] S. Assadi, G. Kol, R. R. Saxena, and H. 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, Los Alamitos, CA, USA, November 2020. IEEE Computer Society. doi:10.1109/FOCS46700.2020.00041.

[bib.bib4] [4] Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear algorithms for ( $\Delta$ + 1) vertex coloring. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 767–786, 2019. doi:10.1137/1.9781611975482.48.

[bib.bib5] [5] Sepehr Assadi, Sanjeev Khanna, and Yang Li. Tight bounds for single-pass streaming complexity of the set cover problem. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 698–711, New York, NY, USA, 2016. Association for Computing Machinery. doi:10.1145/2897518.2897576.

[bib.bib6] [6] Sepehr Assadi and Janani Sundaresan. (noisy) gap cycle counting strikes back: Random order streaming lower bounds for connected components and beyond. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 183–195, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585192.

[bib.bib7] [7] Sujoy Bhore, Fabian Klute, and Jelle J. Oostveen. On streaming algorithms for geometric independent set and clique. In Parinya Chalermsook and Bundit Laekhanukit, editors, Approximation and Online Algorithms, pages 211–224, Cham, 2022. Springer International Publishing. doi:10.1007/978-3-031-18367-6_11.

[bib.bib8] [8] Harry Buhrman and Ronald Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the Annual IEEE Conference on Computational Complexity, pages 120–130, February 2001. doi:10.1109/CCC.2001.933879.

[bib.bib9] [9] Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, and Andrew McGregor. Information cost tradeoffs for augmented index and streaming language recognition. SIAM Journal on Computing, 42(1):61–83, 2013. doi:10.1137/100816481.

[bib.bib10] [10] Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs. In International Colloquium on Automata, Languages and Programming, 2021. URL: https://api.semanticscholar.org/CorpusID:232014583.

[bib.bib11] [11] Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, pages 205–214, New York, NY, USA, 2009. Association for Computing Machinery. doi:10.1145/1536414.1536445.

[bib.bib12] [12] Graham Cormode, Jacques Dark, and Christian Konrad. Independent Sets in Vertex-Arrival Streams. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1–45:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2019.45.

[bib.bib13] [13] Thomas M. Cover and Joy A. Thomas. Elements of information theory (2. ed.). Wiley, 2006.

[bib.bib14] [14] Carsten Damm, Stasys Jukna, and Jirí Sgall. Some bounds on multiparty communication complexity of pointer jumping. In Claude Puech and Rüdiger Reischuk, editors, STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996, Proceedings, volume 1046 of Lecture Notes in Computer Science, pages 643–654. Springer, 1996. doi:10.1007/3-540-60922-9_52.

[bib.bib15] [15] Jacques Dark, Adithya Diddapur, and Christian Konrad. Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting. In Patricia Bouyer and Srikanth Srinivasan, editors, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023), volume 284 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1–24:17, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.FSTTCS.2023.24.

[bib.bib16] [16] Jacques Dark and Christian Konrad. Optimal lower bounds for matching and vertex cover in dynamic graph streams. In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 30:1–30:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.CCC.2020.30.

[bib.bib17] [17] Ashkan Norouzi Fard, Moran Feldman, Ola Svensson, and Rico Zenklusen. Submodular maximization subject to matroid intersection on the fly. In 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, pages 52:1–52:14, 2022. doi:10.4230/LIPICS.ESA.2022.52.

[bib.bib18] [18] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM J. Comput., 38(5):1709–1727, 2008. doi:10.1137/070683155.

[bib.bib19] [19] Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. The one-way communication complexity of submodular maximization with applications to streaming and robustness. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 1363–1374, New York, NY, USA, 2020. Association for Computing Machinery. doi:10.1145/3357713.3384286.

[bib.bib20] [20] Sudipto Guha and Andrew McGregor. Stream order and order statistics: Quantile estimation in random-order streams. SIAM J. Comput., 38(5):2044–2059, 2009. doi:10.1137/07069328X.

[bib.bib21] [21] Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 287–298, 2013. doi:10.1109/CCC.2013.37.

[bib.bib22] [22] Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, and Chengu Wang. Streaming and communication complexity of clique approximation. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 449–460. Springer, 2012. doi:10.1007/978-3-642-31594-7_38.

[bib.bib23] [23] P. Indyk and D. Woodruff. Tight lower bounds for the distinct elements problem. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 283–288, 2003. doi:10.1109/SFCS.2003.1238202.

[bib.bib24] [24] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A property of quantum relative entropy with an application to privacy in quantum communication. J. ACM, 56(6), September 2009. doi:10.1145/1568318.1568323.

[bib.bib25] [25] Daniel M. Kane, Jelani Nelson, and David P. Woodruff. On the exact space complexity of sketching and streaming small norms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pages 1161–1178, USA, 2010. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973075.93.

[bib.bib26] [26] Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating MAX-CUT. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1263–1282. SIAM, 2015. doi:10.1137/1.9781611973730.84.

[bib.bib27] [27] Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, and Samson Zhou. Noisy Boolean Hidden Matching with Applications. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 91:1–91:19, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2022.91.

[bib.bib28] [28] Mikhail Kapralov. Better bounds for matchings in the streaming model. In ACM-SIAM Symposium on Discrete Algorithms, 2012. URL: https://api.semanticscholar.org/CorpusID:448251.

[bib.bib29] [29] Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3311–3320. PMLR, 09–15 June 2019. URL: https://proceedings.mlr.press/v97/kazemi19a.html.

[bib.bib30] [30] Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’95, pages 596–605, New York, NY, USA, 1995. Association for Computing Machinery. doi:10.1145/225058.225277.

[bib.bib31] [31] Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997.

[bib.bib32] [32] F. J. (Florence Jessie) MacWilliams and N. J. A. (Neil James Alexander) Sloane. The theory of error-correcting codes. North-Holland mathematical library ; v. 16. North-Holland Pub. Co., Amsterdam, 1978 - 1977.

[bib.bib33] [33] Guangxu Yang Mi-Ying Huang, Xinyu Mao and Jiapeng Zhang. Breaking square-root loss barriers via min-entropy. Electron. Colloquium Comput. Complex., pages TR24–067, 2024. URL: https://eccc.weizmann.ac.il/report/2024/067/.

[bib.bib34] [34] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. Journal of Computer and System Sciences, 57(1):37–49, 1998. doi:10.1006/jcss.1998.1577.

[bib.bib35] [35] Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. doi:10.1017/9781108671644.

[bib.bib36] [36] Mert Saglam. Tight bounds for data stream algorithms and communication problems. Master’s thesis, Simon Fraser University, 2011.

Optimal Communication Complexity of Chained Index

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Definition 1 (Informal).

Conjecture 2 (​​[12]).

1.1 Our Results

Theorem 3.

1.2 Our Techniques

Prior Techniques

Protocol for index𝒏

Challenges for chain𝒏,𝒌

Our Solution

Biased Index

Independent and Concurrent Work

2 Preliminaries

Notation

Fact 3 (c.f. [32]).

2.1 Communication Complexity Model

Definition 4.

2.2 Information Theoretic Tools

Definition 5 (Shannon Entropy).

Fact 5.

Proposition 6 (Fano’s inequality).

3 The Lower Bound

Definition 7.

Theorem 3 (restated).

3.1 Setting Up the Problem

Notation

Observation 8.

Proof.

3.2 Proof of Lower Bound

Claim 9 (The transcript reveals information about 𝖹.).

Proof.

Lemma 10.

Proof of Theorem 3.

Definition 11.

Lemma 12 (Biased Index).

3.3 Biased Index

Claim 13.

Claim 14.

Observation 15.

Proof.

Claim 16.

Proof.

Proof of Lemma 12.

3.4 Extension to Augmented Chain

Definition 17 (Augmented Chain).

Theorem 18.

4 Applications to Streaming

4.1 Independent Sets

Proposition 19 (Rephrased from [12]).

Corollary 20.

4.2 Submodular Maximization

Proposition 21 (Rephrased from [19]).

Corollary 22.

References

Conjecture 2 ([12]).

Protocol for $\textnormal{{index}}_{n}$

Challenges for $\textnormal{{chain}}_{n,k}$

Claim 9 (The transcript reveals information about ${\mathsf{Z}}$ .).