The communication complexity of Hamming distance mod $4$ 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$.
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\}$.