La complessità della comunicazione della distanza di Hamming Mod $ 4 $

Question

Se Alice e Bob hanno ciascuno un po 'di lunghezza di $ n $, qual è la complessità della comunicazione randomizzata (a una o due vie) per calcolare la distanza di Hamming Mod $ 4 $? Sembra che sia difficile da cercare online, ma sono sicuro che deve essere ben noto.

La complessità di comunicazione deterministica a senso unico è chiaramente lineare poiché Bob può imparare l'intera stringa di Alice dai messaggi che gli invia. Lo fa lanciando ogni bit nella sua corda a sua volta e vedendo se la distanza di Hamming Mod $ 4 $ aumenta o scende (anche Mod $ 4 $).

Se cambiamo la domanda per chiedere la distanza di Hamming Mod $ 2 $, allora Alice deve solo inviare $ 1 $ bit a Bob. Questo è il peso di Hamming della sua stringa Mod $ 2 $.