<p>This is a question from Rao and Yehudayoff's &quot;Communication Complexity and Applications&quot; textbook that I've been thinking about for a while. Suppose Alice has a string <span class="math-container">$x\in\{0,1\}^n$</span> that is known to have more <span class="math-container">$0$</span>s then <span class="math-container">$1$</span>s and Bob has a string <span class="math-container">$y\in\{0,1\}^n$</span> that is known to have more <span class="math-container">$1$</span>s than <span class="math-container">$0$</span>s. Clearly, <span class="math-container">$x\neq y$</span> so there exists some coordinate <span class="math-container">$i\in[n]$</span> where <span class="math-container">$x_i\neq y_i$</span>; Alice and Bob wish to know such an index <span class="math-container">$i$</span>. We want to show that at least <span class="math-container">$2\log n$</span> bits of communication are absolutely necessary.</p>
<p><strong>What I've tried thus far</strong>: at first, I thought this question was somewhat similar to a different question: if instead of the number of <span class="math-container">$0$</span>s and <span class="math-container">$1$</span>s, the guarantees are that <span class="math-container">$\sum x_i = 0\mod{2}$</span> and <span class="math-container">$\sum y_i = 1\mod{2}$</span>, and we wish to compute <span class="math-container">$i$</span> where <span class="math-container">$x_i\neq y_i$</span>, then we can consider the set <span class="math-container">$S=\{(x,x') : \sum x_i = 0 \text{ and } |x-x'|_{hamming}=1\}$</span> then we have the following two properties:</p>
<ul>
<li><span class="math-container">$|S| = n2^{n-1}$</span> which can be seen combinatorially.</li>
<li>If a monochromatic rectangle <span class="math-container">$R$</span> contains <span class="math-container">$r$</span> elements of <span class="math-container">$S$</span> then <span class="math-container">$|R|\geq r^2$</span>. This follows from the fact that if <span class="math-container">$x'\neq x''$</span> and <span class="math-container">$(x,x'), (x,x'')\in S$</span> then <span class="math-container">$(x,x'),(x,x'')$</span> cannot both be in the same <span class="math-container">$i$</span>-monochromatic rectangle as for any <span class="math-container">$x$</span>, there is a unique string that only differs from <span class="math-container">$x$</span> in the <span class="math-container">$i^{th}$</span> coordinate...therefore, if <span class="math-container">$R = A\times B$</span> then <span class="math-container">$|A|,|B|\geq r$</span> so <span class="math-container">$|R|\geq r^2$</span>.</li>
</ul>
<p>The existence of such a set <span class="math-container">$S$</span> can be used to construct a lower bound of <span class="math-container">$2\lceil \log n\rceil$</span>. I tried to find an analogous set for the original problem, but I'm unable to find a set that satisfies both properties. I doubt one exists, because the vast majority of inputs <span class="math-container">$(x,y)$</span> differ in several coordinates (ex. for even <span class="math-container">$n$</span>, <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are guaranteed to differ in at least <span class="math-container">$2$</span> coordinates). Would greatly appreciate any ideas for how to proceed.</p>

CC BY-SA 4.0
2022-11-14T19:03:08.717Z
I don't think $2\log_2 n$ bits are necessary, e.g. consider $n=2$.  Then it must be that $x=00$ and $y=11$, and no communication is necessary.  Maybe $2 \log_2(n) - 2$? And does the problem require both Alice and Bob to know the index $i$, or just one of them?
Neal Young
CC BY-SA 4.0
2022-11-15T21:03:19.080Z
Yes, both Alice and Bob both need to know some index $i$ on which $x_i\neq y_i$ and they should know the same index. I agree the $n=2$ case is trivial, I'll think about if the $\log_2(n)$ bound works for $n\geq 3$.
Ash
CC BY-SA 4.0
2022-11-16T01:46:25.527Z
For $n=4$ I'm pretty sure three bits suffice.  But (oddly) I think that for $n=3$ four bits are necessary (or, to be more precise, in the worst case, Alice has to communicate a bit, Bob has to communicate a bit, Alice can pass, then Bob has to communicate a bit).
Neal Young
<communication-complexity>
communication complexity lower bound for identifying coordinate in which two strings differ
Ash
# communication complexity lower bound for identifying coordinate in which two strings differ

(Asked by: username_0 on 2022-11-14)

This is a question from Rao and Yehudayoff's "Communication Complexity and Applications" textbook that I've been thinking about for a while. Suppose Alice has a string $x\in\{0,1\}^n$ that is known to have more $0$s then $1$s and Bob has a string $y\in\{0,1\}^n$ that is known to have more $1$s than $0$s. Clearly, $x\neq y$ so there exists some coordinate $i\in[n]$ where $x\_i\neq y\_i$; Alice and Bob wish to know such an index $i$. We want to show that at least $2\log n$ bits of communication are absolutely necessary.

**What I've tried thus far**: at first, I thought this question was somewhat similar to a different question: if instead of the number of $0$s and $1$s, the guarantees are that $\sum x\_i = 0\mod{2}$ and $\sum y\_i = 1\mod{2}$, and we wish to compute $i$ where $x\_i\neq y\_i$, then we can consider the set $S=\{(x,x') : \sum x\_i = 0 \text{ and } |x-x'|\_{hamming}=1\}$ then we have the following two properties:

* $|S| = n2^{n-1}$ which can be seen combinatorially.
* If a monochromatic rectangle $R$ contains $r$ elements of $S$ then $|R|\geq r^2$. This follows from the fact that if $x'\neq x''$ and $(x,x'), (x,x'')\in S$ then $(x,x'),(x,x'')$ cannot both be in the same $i$-monochromatic rectangle as for any $x$, there is a unique string that only differs from $x$ in the $i^{th}$ coordinate...therefore, if $R = A\times B$ then $|A|,|B|\geq r$ so $|R|\geq r^2$.

The existence of such a set $S$ can be used to construct a lower bound of $2\lceil \log n\rceil$. I tried to find an analogous set for the original problem, but I'm unable to find a set that satisfies both properties. I doubt one exists, because the vast majority of inputs $(x,y)$ differ in several coordinates (ex. for even $n$, $x$ and $y$ are guaranteed to differ in at least $2$ coordinates). Would greatly appreciate any ideas for how to proceed.

**Tags:** communication-complexity
> **Comments:**
> **username_1**: I don't think $2\log_2 n$ bits are necessary, e.g. consider $n=2$.  Then it must be that $x=00$ and $y=11$, and no communication is necessary.  Maybe $2 \log_2(n) - 2$? And does the problem require both Alice and Bob to know the index $i$, or just one of them?  
> **username_0**: Yes, both Alice and Bob both need to know some index $i$ on which $x_i\neq y_i$ and they should know the same index. I agree the $n=2$ case is trivial, I'll think about if the $\log_2(n)$ bound works for $n\geq 3$.  
> **username_1**: For $n=4$ I'm pretty sure three bits suffice.  But (oddly) I think that for $n=3$ four bits are necessary (or, to be more precise, in the worst case, Alice has to communicate a bit, Bob has to communicate a bit, Alice can pass, then Bob has to communicate a bit).  

---

## 0 answers

