4
$\begingroup$

If Alice and Bob each have a bit string of length $n$, what is the randomized communication complexity (either one or two-way) of computing the Hamming distance mod $4$? It seems this is hard to search for online but I am sure it must be well known.

The one-way deterministic communication complexity is clearly linear as Bob can learn Alice's entire string from the messages she sends him. He does this by flipping each bit in his string in turn and seeing if the Hamming distance mod $4$ goes up or down (also mod $4$).

If we change the question to ask for the Hamming distance mod $2$ then Alice need only send $1$ bit to Bob. That is the Hamming weight of her string mod $2$.

Improve this question
$\endgroup$
9
  • $\begingroup$ Just a "painted" comment. I have no idea what the answer is, but just out of curiosity I made a 5 lines program to show the $\mod 2$ and $\mod 4$ Hamming distances of $(x,y),\; x,y \in [0..255]$. $\mod 2$ (black=0, red=1), and $\mod 4$ (black=0, red=1, green=2, blue=3) ... { "answer_style" : "Wolfram" } :-) $\endgroup$
    – Vor
    Commented Sep 28, 2017 at 10:04
  • $\begingroup$ Are you representing the integers x and y in binary to make them strings? $\endgroup$
    – Simd
    Commented Sep 28, 2017 at 10:21
  • $\begingroup$ @Lembik: yes e.g. x=15, y=5 -> s1=1111 s2=0101 -> Hamming distance = 2. The resulting images are only doubled in size (512x512) to make them more "enjoyable" :-) $\endgroup$
    – Vor
    Commented Sep 28, 2017 at 10:25
  • $\begingroup$ Your lower bound for the deterministic communication complexity isn't correct. You give a way of learning Alice's input using $n$ instantiations of the Hamming distance protocol. This only shows that the latter needs at least one bit. $\endgroup$
    – Yuval Filmus
    Commented Sep 28, 2017 at 12:17
  • 1
    $\begingroup$ @YuvalFilmus Let me check. In the one-way model Alice sends one message to Bob. Bob can now perform any computation he chooses and for as long as he likes. The first thing he does is flip the first bit in his string. Using the one message Alice sent, he computes the Hamming distance mod $4$ before and after flipping the bit. If it goes up when he flips it (or from $3$ to $0$) then he knows Alice had the same bit as him before flipping. Otherwise, he knows Alice had the opposite bit. He then moves on to the second bit using the same message Alice sent him originally. Why is this not right? $\endgroup$
    – Simd
    Commented Sep 28, 2017 at 12:32

1 Answer 1

Reset to default
4
$\begingroup$

Consider the following task $f$: Given $x,y \in \{0,1\}^n$, Alice and Bob need to determine whether $d(x,y) \bmod{4} \in \{0,1\}$, where $d(x,y)$ is the Hamming distance between $x$ and $y$.

Let $M_f$ denote the matrix corresponding to this problem: $M_f(x,y) = 1$ if the answer is Yes, and $M_f(x,y) = -1$ if the answer is No. The discrepancy method shows that $$ R_\epsilon(f) \geq \log \frac{1-2\epsilon}{\lambda_{\max}(M_f)/2^n}. $$ In our case, you can calculate that $\lambda_{\max}(M_f) = 2^{\lceil n/2 \rceil}$ (I checked this for a few $n$ using Krawtchouk polynomials, but presumably there is a simple proof, since all the eigenvalues are nice). For even $n$, this implies that $$ R_\epsilon(f) \geq \log \frac{1-2\epsilon}{2^{-n/2}} = \frac{n}{2} + \log(1-2\epsilon). $$

(When $n$ is odd, the lower bound is slightly worse.)

Exactly the same bound is obtained if we replace the condition $d(x,y) \bmod{4} \in \{0,1\}$ with the condition $d(x,y) \bmod{4} \in \{0,3\}$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Is this a two-way randomized lower bound and how should think about $\epsilon$ in this lower bound? $\endgroup$
    – Simd
    Commented Sep 28, 2017 at 14:47
  • $\begingroup$ The notation $R_\epsilon(f)$ stands for the minimal amount of bits that need to be communicated by a randomized protocol which is correct on each input with probability at least $1-\epsilon$. $\endgroup$
    – Yuval Filmus
    Commented Sep 28, 2017 at 14:54
  • $\begingroup$ Thank you. And just to check, this is for two-way protocols? $\endgroup$
    – Simd
    Commented Sep 28, 2017 at 15:01
  • $\begingroup$ The rule in communication complexity is that protocols are by default two-way. If a protocol is one-way, this will always be mentioned explicitly. $\endgroup$
    – Yuval Filmus
    Commented Sep 28, 2017 at 15:03
  • 1
    $\begingroup$ In the mod 2 case the maximal eigenvalue is $2^n$, so you don't get anything. The method seems to work best when you can convert your problem to a balanced function, so in the case of mod 3 you will actually need to work mod 6, which is possible since obtaining the mod 2 is easy. $\endgroup$
    – Yuval Filmus
    Commented Sep 29, 2017 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.