Editing Communication complexity (section)

== Formal definition ==

Let <math>f: X \times Y \rightarrow Z</math> where we assume in the typical case that <math> X=Y=\{0,1\}^n </math> and <math> Z=\{0,1\}</math>. Alice holds an <math>n</math>-bit string  <math>x \in X</math> while Bob holds an <math>n</math>-bit string  <math>y \in Y</math>. By communicating to each other one [[bit]] at a time (adopting some [[Protocol (computing)|''communication protocol'']] which is agreed upon in advance), Alice and Bob wish to compute the value of <math>f(x,y)</math> such that at least one party knows the value at the end of the communication. At this point the answer can be communicated back so that at the cost of one extra bit, both parties will know the answer. The worst case communication complexity of this communication problem of computing <math>f</math>, denoted as <math> D(f) </math>, is then defined to be

:<math> D(f) = </math> minimum number of bits exchanged between Alice and Bob in the worst case.

As observed above, for any function <math>f: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}</math>, we have <math>D(f) \leq n</math>.
Using the above definition, it is useful to think of the function <math>f</math> as a [[Matrix (mathematics)|matrix]] <math>A</math> (called the ''input matrix'' or ''communication matrix'') where the rows are indexed by <math>x \in X</math> and columns by <math>y \in Y</math>. The entries of the matrix are <math>A_{x,y}=f(x,y)</math>. Initially both Alice and Bob have a copy of the entire matrix <math>A</math> (assuming the function <math>f</math> is known to both parties). Then, the problem of computing the function value can be rephrased as "zeroing-in" on the corresponding matrix entry. This problem can be solved if either Alice or Bob knows both <math>x</math> and <math>y</math>. At the start of communication, the number of choices for the value of the function on the inputs is the size of matrix, i.e. <math>2^{2n}</math>. Then, as and when each party communicates a bit to the other, the number of choices for the answer reduces as this eliminates a set of rows/columns resulting in a [[submatrix]] of <math>A</math>.

More formally, a set <math>R \subseteq X \times Y</math> is called a ''(combinatorial) rectangle'' if whenever <math>(x_1,y_1) \in R</math> and <math>(x_2,y_2) \in R</math> then <math>(x_1,y_2) \in R</math>. Equivalently, <math>R</math> is a combinatorial rectangle if it can be expressed as <math>R = M \times N</math> for some <math>M \subseteq X</math> and <math>N \subseteq Y</math>. Consider the case when <math>k</math> bits are already exchanged between the parties. Now, for a particular <math>h \in \{0,1\}^k</math>, let us define a matrix

:<math>T_{h} = \{ (x, y) : \text{ the }k\text{-bits exchanged on input } (x , y) \text{ is }h\}</math>

Then, <math>T_{h} \subseteq X \times Y</math>, and it is not hard to show that <math>T_{h}</math> is a combinatorial rectangle in <math>A</math>.

=== Example: ''EQ'' ===

We consider the case where Alice and Bob try to determine whether or not their input strings are equal.  Formally, define the ''Equality'' function, denoted <math>EQ : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}</math>, by <math>EQ(x, y) = 1</math> if <math>x = y</math>.  As we demonstrate below, any deterministic communication protocol solving <math>EQ</math> requires <math>n</math> bits of communication in the worst case.  As a warm-up example, consider the simple case of <math>x, y \in \{0, 1\}^3</math>.  The equality function in this case can be represented by the matrix below.  The rows represent all the possibilities of <math>x</math>, the columns those of <math>y</math>.

{| class="wikitable" style="font-family: monospace; text-align: right; margin-left: auto; margin-right: auto; border: none;"
! EQ
! 000
! 001
! 010
! 011
! 100
! 101
! 110
! 111
|-
! 000
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| 0
|-
! 001
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| 0
|-
! 010
| 0
| 0
| 1
| 0
| 0
| 0
| 0
| 0
|-
! 011
| 0
| 0
| 0
| 1
| 0
| 0
| 0
| 0
|-
! 100
| 0
| 0
| 0
| 0
| 1
| 0
| 0
| 0
|-
! 101
| 0
| 0
| 0
| 0
| 0
| 1
| 0
| 0
|-
! 110
| 0
| 0
| 0
| 0
| 0
| 0
| 1
| 0
|-
! 111
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 1
|-
|}

In this table, the function only evaluates to 1 when <math>x</math> equals <math>y</math> (i.e., on the diagonal).  It is also fairly easy to see how communicating a single bit divides someone's possibilities in half.  When the first bit of <math>y</math> is 1, consider only half of the columns (where <math>y</math> can equal 100, 101, 110, or 111).

=== Theorem: ''D(EQ) = n'' ===

Proof. Assume that <math>D(EQ) \leq n-1</math>.  This means that there exists <math>x \neq x'</math> such that <math>(x, x)</math> and <math>(x', x')</math> have the same communication transcript <math>h</math>.  Since this transcript defines a rectangle, <math>f(x, x')</math> must also be 1.  By definition <math>x \neq x'</math> and we know that equality is only true for <math>(a, b)</math> when <math>a = b</math>.  This yields a contradiction.

This technique of proving deterministic communication lower bounds is called the ''fooling set'' technique.<ref name=":0">{{cite book| last1=Kushilevitz | first1=Eyal
| last2=Nisan | first2=Noam  | author-link2=Noam Nisan
| title=Communication Complexity
| publisher=Cambridge University Press
| year=1997
| isbn=978-0-521-56067-2
}}</ref>