In the multiparty communication game (CFL game) of Chandra, Furst, and Lipton [Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, MA, 1983, pp. 94--99] k players collaboratively evaluate a function f(x 0 , . . . , x k -1) in which player i knows all inputs except xi. The players have unlimited computational power. The objective is to minimize communication. In this paper, we study the SIMULTANEOUS MESSAGES (SM) model of multiparty communication complexity. The SM model is a restricted version of the CFL game in which the players are not allowed to communicate with each other. Instead, each of the k players simultaneously sends a message to a referee, who sees none of the inputs. The referee then announces the function value. We prove lower and upper bounds on the SM complexity of several classes of explicit functions. Our lower bounds extend to randomized SM complexity via an entropy argument. A lemma establishing a tradeoff between average Hamming distance and range size for transformations of the Boolean cube might be of independent interest. Our lower bounds on SM complexity imply an exponential gap between the SM model and the CFL model for up to $(\log n)^{1-\epsilon}$ players for any $\epsilon > 0$. This separation is obtained by comparing the respective complexities of the Generalized Addressing Function, GAF G,k , where G is a group of order n. We also combine our lower bounds on SM complexity with the ideas of Håstad and Goldmann [Comput. Complexity, 1 (1991), pp. 113--129] to derive superpolynomial lower bounds for certain depth-2 circuits computing a function related to the GAF function. We prove some counterintuitive upper bounds on SM complexity. We show that {\sf GAF}$_{\mathbb{Z}_2^t,3}$ has SM complexity $O(n^{0.92})$. When the number of players is at least $c\log n$, for some constant c > 0, our SM protocol for {\sf GAF}$_{\mathbb{Z}_2^t,k}$ has polylog(n) complexity. We also examine a class of functions defined by certain depth-2 circuits. This class includes the Generalized Inner Product function and Majority of Majorities. When the number of players is at least 2+log n, we obtain polylog(n) upper bounds for this class of functions.

We generalize the multiparty communication model of Chandra, Furot, nnd Lipton (1983) to functions with b-bit output (6 = 1 in (he CFL model), We allow the parties to receive up to b -1 bits of information from an all-powerful benevolent Helper who can see all lhc Input.WC construct families of explicit functions for which fl(n/c") bits of communication are required to find the "missing bit," where n ia the length of each player's input and H is the number of players, This extends the results of Babal, Nisan, Szegedy (1992), As a consequence we settle the old problem of separatlng the one-wny vs. multiround communication complexities (in the CFL sense) for h 5 (1 -6) log 9~ players, extending a result of Nionn and Wigdcrson (1991) who demonstrated this separation for 12 z 3 players.As a by-product we obtain S2(n/ck) lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit boolean functions (not derivable from BNS).The proofs exploit the interplay between two new theories of multicolor discrepancy; discrete Fourier analysis is the basic tool.We nlao include a previously unpublished lower bound by A. Wigdernon regarding the one-way complexity of the 3-party pointer jumping function,

We solve a 17 year old problem of A.C.C. Yao (1979). In the two-player communication model introduced by Yao in 1979, Alice and Bob wish to collaboratively evaluate a function f(x,y) in which Alice knows only input x and Bob knows only input y. Both players have unlimited computational power. The objective is to minimize the amount of communication. Yao (1979) also introduced an oblivious version of this communication game which we call the simultaneous messages (SM) model. The difference is that in the SM model, Alice and Bob don't communicate with each other. Instead, they simultaneously send messages to a referee, who sees none of the input. The referee then announces the function value. The deterministic two-player SM complexity of any function is straight forward to determine. Yao suggested the randomized version of this model, where each player has access to private coin flips. Our main result is that the order of magnitude of the randomized SM complexity of any function f is at least the square root of the deterministic SM complexity of f. We found this result in February 1996, independently but subsequently to I. Newman and M. Szegedy (1996) who obtained this lower bound for the special case of the function. Our proof is entirely different from and considerably simpler than the Newman-Szegedy solution. A proof similar in spirit to ours, was found by J. Bourgain and A. Wigderson simultaneously to us (unpublished); we include an outline of their proof. The quadratic reduction actually does occur for the function. We give a new proof of this fact. This result, combined with our main result, settles Yao's question, asking the exact randomized SM complexity of the equality function. The lower bound proof uses the probabilistic method; the upper bound uses linear algebra. We also give a constructive proof that O(log n) public coins reduce the complexity of to constant.