The cost of the missing bit: Communication complexity with help

We generalize the multiparty communication model of Chandra, Furst, and Lip ton (1983) to functions with b-bit output (b = 1 in the CFL model). We allo w the players to receive up to b - 1 bits of information from an all-powerf ul benevolent Helper who can see all the input. Extending results of Babai, Nisan, and Szegedy (1992) to this model, we construct families of explicit functions for which Omega (n/c(k)) bits of communication are required to f ind the "missing bit," where n is the length of each player's input and k i s the number of players. As a consequence we settle the problem of separati ng the one-way vs. multiround communication complexities (in the CFL sense) for k less than or equal to (1 - is an element of) log n players, extendin g a result of Nisan and Wigderson (1991) who demonstrated this separation f or k = 3 players. As a by-product we obtain Omega (n/c(k)) lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit b oolean functions (not derivable from BNS). The proofs exploit the interplay between two concepts of multicolor discrepancy; discrete Fourier analysis is the basic tool. We also include an unpublished lower bound by A. Wigders on regarding the one-way complexity of the 3-party pointer jumping function .