Abstract:
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.