Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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?
