Return to Question

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 message 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$.

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$.

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 deterministic communication complexity is clearly linear as Bob can learn Alice's entire string from the message 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$.

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 message 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$.

If Alice and Bob each have a bit string of length $n$, what is the 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.

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$.

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 deterministic communication complexity is clearly linear as Bob can learn Alice's entire string from the message 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$.