ON COMMUNICATION COMPLEXITY OF FECTOR-VALUED FUNCTIONS

New upper and lower bounds on the two-way communication complexity of abstract functions g: X x Y --> L give tight bounds, when applied to v ector-valued functions f(n) = (f1, ..., f(n)): X(n) x Y(n) --> L(n), i f the alphabets are small. For the set-intersection function, an optim al protocol is presented. It is based on a simple new idea applicable also to abstract functions. The two-way communication complexities of all other Boolean functions are also determined. The results are exten ded to meets in abstract lattices and to a probabilistic model.