<p>The reason is that a lower bound on the worst-case complexity automatically implies a lower bound on the expected complexity, so there is no reason to prove the latter.</p>

<p>To see the implication, observe that every randomized protocol with expected complexity <span class="math-container">$c$</span> and error probability <span class="math-container">$\varepsilon$</span> can be transformed into a randomized protocol with <em>worst-case</em> complexity <span class="math-container">$c/\varepsilon$</span> and error probability <span class="math-container">$2\varepsilon$</span>: The new protocol simulates the old protocol, but forces the simulation to halt after <span class="math-container">$c/\varepsilon$</span> bits have been transmitted. By Markov inequality, a forced halting occurs with probability at most <span class="math-container">$\varepsilon$</span>, so it adds at most <span class="math-container">$\varepsilon$</span> to the original error probability.</p>

<p>Since error probability can be amplified, it follows that every randomized protocol with expected complexity <span class="math-container">$c$</span> and constant error probability can be transformed into a randomized protocol with <em>worst-case</em> complexity <span class="math-container">$O(c)$</span> and the same error probability. Thus, if we show that there is no randomized protocol with worst-case communication <span class="math-container">$O(c)$</span> and constant error probability that computes a function <span class="math-container">$f$</span>, the same holds for protocols with expected communication <span class="math-container">$O(c)$</span>.</p>

CC BY-SA 4.0
2020-02-25T15:15:14.587Z
2020-02-25T15:15:14.587Z
Or Meir
<p>In the set disjointness problem of 2-party communication complexity, Alice and Bob are both given an <span class="math-container">$n$</span>-bit string as input; denoted by <span class="math-container">$X$</span> for Alice's input, and <span class="math-container">$Y$</span> for Bob's input. They need to output "no" if and only if there exists an index <span class="math-container">$i$</span> such that <span class="math-container">$X[i]=Y[i]=1$</span>, otherwise they should output "yes".</p>

<p>The seminal paper <a href="http://people.seas.harvard.edu/~madhusudan/courses/Spring2016/papers/BJKS.pdf" rel="noreferrer">An information statistics approach to data stream and communication complexity</a> shows a lower bound of <span class="math-container">$\Omega(n)$</span> bits for this problem on the <em>worst case</em> length of the transcript <span class="math-container">$\Pi$</span> sent between Alice and Bob. At the end of their argument, the authors show this by using that <span class="math-container">$|\Pi| \ge H[\Pi]$</span>, where <span class="math-container">$|\Pi|$</span> is the transcript length and <span class="math-container">$H[\Pi]$</span> is the entropy of the transcript. </p>

<p>I was wondering why the authors didn't show the significantly stronger statement that the <strong>expected</strong> communication complexity is at least <span class="math-container">$\Omega(n)$</span>. This holds because even the expected length of the transcript is at least as long as <span class="math-container">$H[\Pi]$</span> (by the converse of Shannon's coding theorem, right?). </p>

<p>Actually, all lower bounds that I've seen in communication complexity seem to be shown only for the worst case length. </p>

<p>Is there some reason why the expected communication complexity isn't considered that I'm missing? </p>

CC BY-SA 4.0
2020-02-22T12:16:29.733Z
The problem is that we use a specific distribution of inputs to show a lower bound on the entropy. For many distributions $\mathrm{DISJ}_n$ can be solved in $o(n)$ communication. This is the case for all distributions where $X$ and $Y$ are picked independently (http://brahma.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/papers/BabaiFS1986.pdf) For uniform distribution of the inputs it is easy to see that Alice and Bob can split input into $\sqrt{n}$ chunks, compute the number of 1-bits in each chunk and with good probability there exists a chunk with the total number of 1-bits $> \sqrt{n}$.
Artur Riazanov
CC BY-SA 4.0
2020-02-24T04:05:33.357Z
Just to see if I understand your comment correctly: you're saying the reason why these results are stated as worst case rather than expected value, is that the expected value is only relevant w.r.t. a specific distribution, whereas the worst case is universally true?
cstheory_student1
CC BY-SA 4.0
2020-02-24T15:38:30.800Z
Exactly, usually the key of the proof is to figure out what distribution of inputs to consider.
Artur Riazanov
CC BY-SA 4.0
2020-02-25T15:07:36.193Z
@ArturRiazanov Not exactly. Expected communication complexity can be defined even when there is no distribution over the inputs - in this case, the expectation is over the coin tosses of the protocol.
Or Meir
CC BY-SA 4.0
2020-02-25T16:21:38.580Z
@OrMeir Oh, makes sense, for some reason I assumed that the question was about this setting.
Artur Riazanov
<it.information-theory><communication-complexity>
Expected vs worst-case communication complexity
cstheory_student1
# Expected vs worst-case communication complexity

(Asked by: username_0 on 2020-02-21)

In the set disjointness problem of 2-party communication complexity, Alice and Bob are both given an $n$-bit string as input; denoted by $X$ for Alice's input, and $Y$ for Bob's input. They need to output "no" if and only if there exists an index $i$ such that $X[i]=Y[i]=1$, otherwise they should output "yes".

The seminal paper [An information statistics approach to data stream and communication complexity](http://people.seas.harvard.edu/~madhusudan/courses/Spring2016/papers/BJKS.pdf) shows a lower bound of $\Omega(n)$ bits for this problem on the *worst case* length of the transcript $\Pi$ sent between Alice and Bob. At the end of their argument, the authors show this by using that $|\Pi| \ge H[\Pi]$, where $|\Pi|$ is the transcript length and $H[\Pi]$ is the entropy of the transcript.

I was wondering why the authors didn't show the significantly stronger statement that the **expected** communication complexity is at least $\Omega(n)$. This holds because even the expected length of the transcript is at least as long as $H[\Pi]$ (by the converse of Shannon's coding theorem, right?).

Actually, all lower bounds that I've seen in communication complexity seem to be shown only for the worst case length.

Is there some reason why the expected communication complexity isn't considered that I'm missing?

**Tags:** it.information-theory, communication-complexity
> **Comments:**
> **username_1**: The problem is that we use a specific distribution of inputs to show a lower bound on the entropy. For many distributions $\mathrm{DISJ}_n$ can be solved in $o(n)$ communication. This is the case for all distributions where $X$ and $Y$ are picked independently (http://brahma.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/papers/BabaiFS1986.pdf) For uniform distribution of the inputs it is easy to see that Alice and Bob can split input into $\sqrt{n}$ chunks, compute the number of 1-bits in each chunk and with good probability there exists a chunk with the total number of 1-bits $> \sqrt{n}$.  
> **username_0**: Just to see if I understand your comment correctly: you're saying the reason why these results are stated as worst case rather than expected value, is that the expected value is only relevant w.r.t. a specific distribution, whereas the worst case is universally true?  
> **username_1**: Exactly, usually the key of the proof is to figure out what distribution of inputs to consider.  
> **username_2**: @ArturRiazanov Not exactly. Expected communication complexity can be defined even when there is no distribution over the inputs - in this case, the expectation is over the coin tosses of the protocol.  
> **username_1**: @OrMeir Oh, makes sense, for some reason I assumed that the question was about this setting.  

---

## 1 answers

### Answer by username_2 on 2020-02-25. Score: 4 | Accepted answer

The reason is that a lower bound on the worst-case complexity automatically implies a lower bound on the expected complexity, so there is no reason to prove the latter.

To see the implication, observe that every randomized protocol with expected complexity $c$ and error probability $\varepsilon$ can be transformed into a randomized protocol with *worst-case* complexity $c/\varepsilon$ and error probability $2\varepsilon$: The new protocol simulates the old protocol, but forces the simulation to halt after $c/\varepsilon$ bits have been transmitted. By Markov inequality, a forced halting occurs with probability at most $\varepsilon$, so it adds at most $\varepsilon$ to the original error probability.

Since error probability can be amplified, it follows that every randomized protocol with expected complexity $c$ and constant error probability can be transformed into a randomized protocol with *worst-case* complexity $O(c)$ and the same error probability. Thus, if we show that there is no randomized protocol with worst-case communication $O(c)$ and constant error probability that computes a function $f$, the same holds for protocols with expected communication $O(c)$.


---

