TR01-019 Authors: Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

Publication: 5th March 2001 14:15

Downloads: 1462

Keywords:

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 ways to approximate it.

Our work is related to the Direct SUm Conjecture.