2
$\begingroup$

Let $n > 10^6$ be a large square. Bob knows $n$ pairs $(x_1, y_1),(x_2, y_2), \ldots ,(x_n, y_n)$ of binary vectors. Each vector $x_i$ and $y_i$ is length $n$ and for each $i$, the Hamming distance between $x_i$ and $y_i$ is at least $n-0.5\sqrt{n}$. Alice knows one of the vectors of each pair, that is, she knows $z_1, z_2, \ldots , z_n$ where for each $i$, $z_i$ is either equal to $x_i$ or $y_i$. Can Alice send Bob less than $10n$ bits that will enable him to identify all the $n$ vectors $z_i$ among his $2n$ vectors? Let's assume that Bob and Alice can agree on a communication protocol ahead of time, and they both know in advance that the Hamming distance between each pair of vectors of Bob will be at least $n-0.5\sqrt{n}$.

I'm pretty new to information theory, but there seems to be a counting argument for the above problem. How would one tackle this problem?

$\endgroup$
3
  • $\begingroup$ Does Alice know $z_i =x_i$ OR $z_i = y_i$ ? If she knows then you just have to send $1$ bit for each $i$ to indicate whether $z_i = x_i$ or $z_i = y_i$ ? Totally $n$ bits. $\endgroup$
    – Balaji sb
    Mar 30, 2023 at 6:40
  • $\begingroup$ How about sending the component of $z_i$ (say $j_i^{th}$ bit of $z_i$) in which $x_i$ and $y_i$ differ for each $i$. This way you just have to send $n$ bits ? $\endgroup$
    – Balaji sb
    Mar 30, 2023 at 8:30
  • $\begingroup$ but each pair $x_i,y_i$ differ in $\geq n - \sqrt{n}/2$ bits, so that is not enough. $\endgroup$
    – kodlu
    Mar 31, 2023 at 1:59

1 Answer 1

1
$\begingroup$

For each of the $n$ pairs, use one bit to state whether the vector that Alice has is the "correct" one. This makes $n$ bits. Say this bit being $0$ means the vector is correct. So, $001\cdots$ in the beginning means the first two vectors are the correct ones while the third is NOT correct and then you check the vector of length $n-1$ bits following the $1$ bit you see [this is a comma free code]. I prove below that $n-1$ bits is sufficient for the differential info about where the vectors do not match.

If all of them are correct, you send $n$ 0's and the protocol ends.

At worst, all of them are the "incorrect" vector. Then one needs to encode the positions where the bits "have to flip". If the Hamming distance between the pairs is at least $n-\frac{\sqrt{n}}{2}$ then one can encode the positions where the two vectors are the same, i.e., a subset of size $\leq n- \frac{\sqrt{n}}{2}.$

This encoding takes less than or equal to $$ \log_2 \binom{n}{n-\frac{\sqrt{n}}{2}}\leq \log_2 \binom{n}{n/2}\leq \log_2 2^{n-1}\leq n-1 $$ bits per vector pair by a well known bound on the middle binomial coefficient.

I believe the given fact that $n$ is a square is to stop you worrying about ceiling functions which would contribute extra fractional bits to the argument.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .