<p>Suppose Alice always sends exactly <span class="math-container">$k$</span> bits to Bob during the protocol.  On average, how many possible candidates for her <span class="math-container">$n$</span>-bit string are consistent with the communication transcript?  What does that tell you about the probability that Bob guesses which one of those candidates is the correct one?</p>

CC BY-SA 4.0
2021-07-16T04:45:47.777Z
Ah, thanks a lot!
polar_bear_cheese
CC BY-SA 4.0
2021-07-16T03:45:51.747Z
2021-07-16T03:45:51.747Z
D.W.
<p>This seems like a folklore claim but I cannot find any reference to it. If Alice has a bit-string of length <span class="math-container">$n$</span> where each entry is independently set to 0 or 1 equiprobably, and Bob's goal is to reconstruct the string with a success probability at least 0.9. What is the simplest way to show that the randomized communication complexity (multiple rounds are allowed) is <span class="math-container">$\Omega(n)$</span>?</p>
<p>One can use an overkilled proof: such a protocol will lead to a protocol for Disjointness and we know that Disjointness requires <span class="math-container">$\Omega(n)$</span> bits of communication.</p>

<reference-request><communication-complexity>
Communication complexity of reconstructing a random bit-string of length $n$
polar_bear_cheese
# Communication complexity of reconstructing a random bit-string of length $n$

(Asked by: username_0 on 2021-07-16)

This seems like a folklore claim but I cannot find any reference to it. If Alice has a bit-string of length $n$ where each entry is independently set to 0 or 1 equiprobably, and Bob's goal is to reconstruct the string with a success probability at least 0.9. What is the simplest way to show that the randomized communication complexity (multiple rounds are allowed) is $\Omega(n)$?

One can use an overkilled proof: such a protocol will lead to a protocol for Disjointness and we know that Disjointness requires $\Omega(n)$ bits of communication.

**Tags:** reference-request, communication-complexity

---

## 1 answers

### Answer by username_1 on 2021-07-16. Score: 3 | Accepted answer

Suppose Alice always sends exactly $k$ bits to Bob during the protocol. On average, how many possible candidates for her $n$-bit string are consistent with the communication transcript? What does that tell you about the probability that Bob guesses which one of those candidates is the correct one?

> **Comments:**
> **username_0**: Ah, thanks a lot!  

---

