Portal de Periódicos da CAPES

Simultaneous messages vs. communication

1995; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-59042-0_88

1611-3349

László Babai, Peter G. Kimmel, Satyanarayana V. Lokam,

Mobile Ad Hoc Networks

In the multiparty communication game introduced by Chandra, Furst, and Lipton [CFL] (1983), k players wish to evaluate collaboratively a function f(x 0,⋯, x k−1 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)1−∈ players, for any ∈>0. The separation is obtained by comparing the respective complexities of the generalized addressing function, GAFn,k, in each model. This work is motivated by an approach suggested by the results of Håstad & Goldmann (1991), Yao (1990), and Beigel & Tarui (1991) to separate ACC from complexity classes containing it.