On communication complexity of vector-valued functions
Rudolf Ahlswede, Ning Cai · IEEE Transactions on Information Theory · 1994
New upper and lower bounds on the two-way communication complexity of abstract functions g:/spl Hscr//spl times//spl Yscr//spl rarr//spl Zscr/ give tight bounds, when applied to vector-valued functions f/sup n/(f/sub 1/,...,f/sub n/):/spl Hscr//sup u//spl times//spl Yscr//sup n//spl rarr//spl Zscr//sup n/, if the alphabets are small. For the set-intersection function, an optimal 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 extended to meets in abstract lattices and to a probabilistic model.>