Editing Communication complexity (section)

=== Example: GH ===
For yet another example of randomized communication complexity, we turn to an example known as the ''[[gap-Hamming problem]]'' (abbreviated ''GH''). Formally, Alice and Bob both maintain binary messages, <math>x,y \in \{-1, +1\}^n</math> and would like to determine if the strings are very similar or if they are not very similar. In particular, they would like to find a communication protocol requiring the transmission of as few bits as possible to compute the following partial Boolean function, 

:<math>
\text{GH}_n(x, y) := 
\begin{cases}
-1 & \langle x, y \rangle \leq \sqrt{n} \\
+1 & \langle x, y \rangle \geq \sqrt{n}. 
\end{cases} 
</math> 

Clearly, they must communicate all their bits if the protocol is to be deterministic (this is because, if there is a deterministic, strict subset of indices that Alice and Bob relay to one another, then imagine having a pair of strings that on that set disagree in <math>\sqrt{n} - 1</math> positions. If another disagreement occurs in any position that is not relayed, then this affects the result of <math> \text{GH}_n(x, y)</math>, and hence would result in an incorrect procedure. 

A natural question one then asks is, if we're permitted to err <math>1/3</math> of the time (over random instances <math> x, y</math> drawn uniformly at random from <math> \{-1, +1\}^n </math>), then can we get away with a protocol with fewer bits? It turns out that the answer somewhat surprisingly is no, due to a result of Chakrabarti and Regev in 2012: they show that for random instances, any procedure which is correct at least <math>2/3</math> of the time must send <math>\Omega(n)</math> bits worth of communication, which is to say essentially all of them.