|
Abstract : |
Abstract. In the multiparty communication game introduced by Chandra, Furst, and Lipton [CFL] (1983), k players wish to evaluate collaboratively a function f(x0; : : : ; xk\Gamma1) for which player i sees all inputs except x i: The players have unlimited computational power. The objective is to minimize the amount of communication. We consider a restricted version of the multiparty communication game which we call the simultaneous messages model. The difference is that in this model, each of the k players simultaneously sends a message to a referee, who sees none of the input. The referee then announces the function value. We show demonstrate an exponential gap between the Simultaneous Messages and the Communication models for up to (log n), |
