Editing Communication complexity (section)

=== Example: EQ ===

Returning to the previous example of ''EQ'', if certainty is not required, Alice and Bob can check for equality using only {{tmath|O(\log n)}} messages.  Consider the following protocol:  Assume that Alice and Bob both have access to the same random string <math>z \in \{0,1\}^n</math>. Alice computes <math>z \cdot x</math> and sends this bit (call it ''b'') to Bob. (The <math>(\cdot)</math> is the [[dot product]] in [[finite field#Some small finite fields|GF(2)]].) Then Bob compares ''b'' to <math>z \cdot y</math>. If they are the same, then Bob accepts, saying ''x'' equals ''y''. Otherwise, he rejects.

Clearly, if <math>x = y</math>, then <math>z \cdot x = z \cdot y</math>, so <math>Prob_z[Accept] = 1</math>. If ''x'' does not equal ''y'', it is still possible that <math>z \cdot x = z \cdot y</math>, which would give Bob the wrong answer. How does this happen?

If ''x'' and ''y'' are not equal, they must differ in some locations:

:<math>\begin{cases}
x = c_1 c_2 \ldots p   \ldots p'  \ldots x_n \\
y = c_1 c_2 \ldots q   \ldots q'  \ldots y_n \\
z = z_1 z_2 \ldots z_i \ldots z_j \ldots z_n 
\end{cases}</math>

Where {{mvar|x}} and {{mvar|y}} agree, <math>z_i * x_i = z_i * c_i = z_i * y_i</math> so those terms affect the dot products equally. We can safely ignore those terms and look only at where {{mvar|x}} and {{mvar|y}} differ. Furthermore, we can swap the bits <math>x_i</math> and <math>y_i</math> without changing whether or not the dot products are equal. This means we can swap bits so that {{mvar|x}} contains only zeros and {{mvar|y}} contains only ones:

:<math>\begin{cases}
x' = 0   0   \ldots 0   \\
y' = 1   1   \ldots 1   \\
z' = z_1 z_2 \ldots z_{n'} 
\end{cases}</math>

Note that <math>z' \cdot x' = 0</math> and <math>z' \cdot y' = \Sigma_i z'_i</math>. Now, the question becomes: for some random string <math>z'</math>, what is the probability that <math>\Sigma_i z'_i = 0</math>?  Since each <math>z'_i</math> is equally likely to be {{val|0}} or {{val|1}}, this probability is just <math>1/2</math>. Thus, when {{mvar|x}} does not equal {{mvar|y}},
<math>Prob_z[Accept] = 1/2</math>. The algorithm can be repeated many times to increase its accuracy. This fits the requirements for a randomized communication algorithm.

This shows that ''if Alice and Bob share a random string of length n'', they can send one bit to each other to compute <math>EQ(x,y)</math>. In the next section, it is shown that Alice and Bob can exchange only {{tmath|O(\log n)}} bits that are as good as sharing a random string of length ''n''. Once that is shown, it follows that ''EQ'' can be computed in {{tmath|O(\log n)}} messages.