Communication Complexity

Of course they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the Function , but the idea here is to find clever ways of calculating f with less than n bits of communication.

This abstract problem is relevant in many contexts: in VLSI circuit design, for example, one wants to minimize energy used by decreasing the amount of electric signals required between the different components during a distributed computation. The problem is also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.

FORMAL DEFINITION

Let

f

: X

imes

ightarrow

Z where we assume in the typical case that

X=Y=\{0,1\}^n

and

Z=\{0,1\}

. Alice draws a n-bit string

x

\in

X while Bob draws a n-bit string

y

\in

Y. By communicating to each other one bit at a time (adopting some Communication Protocol ), Alice and Bob want to compute the value of

f(x,y)

such that at least one party knows the value at the end of the communication. It is trivial to see that once one party knows the answer, with one more bit exchange, both parties know the answer. The worst case communication complexity of this communication protocol, denoted as

D(f)

, is then defined to be

:

D(f) =

minimum number of bits exchanged between Alice and Bob in the worst case

Using the above definition, it is useful to think of the function

f

as a Matrix

A

(called as the input matrix) where each row of the matrix corresponds to

x

\in

X and each column

y

\in

Y. An entry in the input matrix is

A_{\mathrm{x,y}}=f(x,y)

. Initially both Alice and Bob have a copy of the entire matrix A (assuming the function

f

is known to both). 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

x

and

y

. 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

n^2

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

More formally, a set R

\subseteq

imes

Y is called a rectangle if whenever

(x_1,y_1)

\in

R and

(x_2,y_2)

\in

R then

(x_1,y_2)

\in

R. Equivalently, R can also be viewed as a submatrix of the input matrix A such that R = M

imes

N where M

\subseteq

X and N

\subseteq

Y. Consider the case when

k

bits are already exchanged between the parties. Now, for a particular

h

\in

\{0,1\}^k

, let us define a matrix

:

T_{\mathrm{h}} = \{ (x, y) :

the k-bits exchanged on input

(x , y)

h

}

Then,

T_{\mathrm{h}}

\subseteq

imes

Y, and

T_{\mathrm{h}}

is a rectangle and a submatrix of A.

Example: EQ

We consider the case where Alice and Bob try to determine if they both have the same string. That is, we are trying to determine if

x

is equal to

y

. It is easy to prove that the equality problem (EQ) will always require you to communicate

n

bits in the worst case if you want to be absolutely sure

x

and

y

are equal.
Consider the simple case of

x

and

y

being 3 bits. The equality function in this case can be represented by the matrix below. The rows representing all the possibilities of

x

, the columns those of

y

.

As you can see, the function only holds where

x

equals

y

(on the diagonal). It is also fairly easy to see how communicating a single bit divides your possibilities in half. If you know that the first bit of

y

is 1, you only need to consider half of the columns (where

y

can equal 100, 101, 110, or 111).

Theorem: $D(EQ) = n$ .

Proof. Assume that

D(EQ) \leq n-1

. This means that there exists an

(x, x)

and an

(x', x')

having the same history,

h

. Since this history defines a rectangle,

f(x, x')

must also be 1. By definition

x 
eq x'

and we know that equality is only true for

(a, b)

when

a = b

. Thus, we have a contradiction.

Intuitively, for

D(EQ)

less than

n

, we need to be able to define a rectangle in the EQ matrix greater in size than a single cell. All of the cells in this rectangle must contain 1 for us to be able to generalize that this rectangle equals 1. It is not possible to form such a rectangle in the equality matrix.

RANDOMIZED CC

In the above definition, we are concerned with the number of bits that must be ''detereministically'' transmitted between two parties. If both the parties are given access to a random number generator, can they determine the value of

f

with much less information exchanged? Yao, in his seminal paper {Link without Title} answers this question by defining randomized communication complexity.

A randomized protocol

R

for a function

f

has two-sided error.

:

\ge rac{1}{2}, extrm{if }\, f(x,y) = 0

\ge rac{1}{2}, extrm{if }\, f(x,y) = 1

A randomized protocol is a deterministic protocol that uses an extra random string in addition to its normal input. There are two models for this: a ''public string'' is a random string that is known by both parties beforehand, while a ''private string'' is generated by one party and must be communicated to the other party. A theorem presented below shows that any public string protocol can be simulated by a private string protocol that uses O(log n) additional bits compared to the original.

The randomized complexity is simply defined as the number of bits exchanged in such a protocol.

Note that it is also possible to define a randomized protocol with one-sided error, and the complexity is defined similarly.

Example: EQ

Returning to the previous example of ''EQ'', if certainty is not required, Alice and Bob can check for equality using only O(log n) messages. Consider the following protocol: Assume that Alice and Bob both have access to the same random string

z \in \{0,1\}^n

. Alice computes

z \cdot x

and sends this bit (call it b) to Bob. (The

(\cdot)

is the Dot Product in GF(2) .) Then Bob compares b to

z \cdot y

. If they are the same, then Bob accepts, saying x equals y. Otherwise, he rejects.

Clearly, if

x = y

, then

z \cdot x = z \cdot y

, so

Prob_z

{Link without Title} = 1. If x does not equal y, it is still possible that

z \cdot x = z \cdot y

, which would give Bob the wrong answer. How does this happen?

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

:

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

x_i = z_i --- c_i = z_i --- y_i so those terms affect the dot products equally. We can safely ignore those terms and look only at where $x$ and $y$ differ. Furthermore, we can swap the bits $x_i$ and $y_i$ without changing whether or not the dot products are equal. This means we can swap bits so that $x$ contains only zeros and $y$ contains only ones:

x' = 0   0   \ldots 0

y' = 1   1   \ldots 1

z' = z_1 z_2 \ldots z_{n'}

Note that

z' \cdot x' = 0

and

z' \cdot y' = \Sigma_i z'_i

. Now, the question becomes: for some random string

z'

, what is the probability that

\Sigma_i z'_i = 0

? Since each

z'_i

is equally likely to be

0

1

, this probability is just

1/2

. Thus, when

x

does not equal

y

Prob_z

{Link without Title} = 1/2. 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

EQ(x,y)

. In the next section, it is shown that Alice and Bob can exchange only 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 O(log n) messages.

Public Coins vs. Private Coins

It is easier to create random protocols when both parties have access to the same random string (shared string protocol). It is still possible to use these protocols even when the two parties don't share a random string (private string protocol) with a small communication cost. Any shared string random protocol using an

n

-bit string can be simulated by a private string protocol that uses an extra O(log n) bits.

Intuitively, we can find some set of strings that has enough randomness in it to run the random protocol with only a small increase in error. This set can be shared beforehand, and instead of drawing a random string, Alice and Bob need only agree on which string to choose from the shared set. This set is small enough that the choice can be communicated efficiently. A formal proof follows.

Consider some random protocol P with a maximum error rate of 0.1. Let

R

100n

strings of length

n

, numbered

r_1, r_2, ..., r_{100n}

. Given such an

R

, define a new protocol

P'_R

which randomly picks some

r_i

and then runs P using

r_i

as the shared random string. It takes O(log 100n) = O(log n) bits to communicate the choice of

r_i

.

Let us define

p(x,y)

and

p'_R(x,y)

to be the probabilities that

P

and

P'_R

compute the correct value for the input

(x,y)

.

For a fixed

(x,y)

, we can use Hoeffding's Inequality to get the following equation:

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT COMMUNICATION COMPLEXITY

	complexity classes

Information About

Communication Complexity