<p>This is a basic exercise and is not research level.  Hints:</p>
<p>How many possible answers from Bob would be accepted as valid?  How many possible strings might Alice have chosen?  From this, what can you conclude about the number of bits of entropy that must be communicated?</p>

CC BY-SA 4.0
2022-10-22T01:41:26.043Z
2022-10-22T01:41:26.043Z
D.W.
<p>Suppose Alice has a bit string of length <span class="math-container">$n$</span> where <span class="math-container">$n/2$</span> bits are chosen uniformly at random to be 1's; and the rest are 0's. Alice sends a message to Bob.</p>
<p>If Bob needs to reconstruct the bit string, then <span class="math-container">$\Omega(n)$</span> communication is needed.</p>
<p>However, suppose Bob only needs to reconstruct at least <span class="math-container">$0.99n$</span> bits correctly (without knowing which bits are correct). Would this lower bound still hold?</p>

<communication-complexity>
Communication complexity of correctly recovering 99% of a random bit string
polar_bear_cheese
# Communication complexity of correctly recovering 99% of a random bit string

(Asked by: username_0 on 2022-10-21)

Suppose Alice has a bit string of length $n$ where $n/2$ bits are chosen uniformly at random to be 1's; and the rest are 0's. Alice sends a message to Bob.

If Bob needs to reconstruct the bit string, then $\Omega(n)$ communication is needed.

However, suppose Bob only needs to reconstruct at least $0.99n$ bits correctly (without knowing which bits are correct). Would this lower bound still hold?

**Tags:** communication-complexity


---

## 1 answers

### Answer by username_1 on 2022-10-22. Score: 1 | Accepted answer

This is a basic exercise and is not research level. Hints:

How many possible answers from Bob would be accepted as valid? How many possible strings might Alice have chosen? From this, what can you conclude about the number of bits of entropy that must be communicated?


---

