All reports by Author Bala Kalyansundaram:

__
TR01-019
| 2nd March 2001
__

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet#### The Communication Complexity of Enumeration, Elimination, and Selection

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

Normally, communication Complexity deals with how many bits

Alice and Bob need to exchange to compute f(x,y)

(Alice has x, Bob has y). We look at what happens if

Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n

and they want to compute f(x_1,y_1)... f(x_n,y_n).

THis seems hard. We look at various ...
more >>>