7
$\begingroup$

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 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?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ 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 (brahma.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/papers/…) 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}$. $\endgroup$
    – Artur Riazanov
    Feb 22, 2020 at 12:16
  • 1
    $\begingroup$ 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? $\endgroup$
    – cstheory_student1
    Feb 24, 2020 at 4:05
  • $\begingroup$ Exactly, usually the key of the proof is to figure out what distribution of inputs to consider. $\endgroup$
    – Artur Riazanov
    Feb 24, 2020 at 15:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – Or Meir
    Feb 25, 2020 at 15:07
  • $\begingroup$ @OrMeir Oh, makes sense, for some reason I assumed that the question was about this setting. $\endgroup$
    – Artur Riazanov
    Feb 25, 2020 at 16:21

1 Answer 1

Reset to default
4
$\begingroup$

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)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.