Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams

In a k -party communication problem, the k players with inputs x(1), x(2),. .. , x(k) want to evaluate a function f(x(1), x(2),... , x(k)) using as little communication as possible. We consider the message-passing model, in which the inputs are partitioned in an arbitrary, possibly worst-case manner, among a smaller number t of players (t < k). The t -player communication cost of computing f can only be smaller than the k -player communication cost, since the t players can trivially simulate the k -player protocol. But how much smaller can it be? We study deterministic and randomized protocols in the one-way model, and provide separations for product input distributions, which are optimal for low error probability protocols. We also provide much stronger separations when the input distribution is non-product.