Cost of the missing bit: Communication complexity with help

We generalize the multiparty communication model of Chandra, Furst, and Lipton (1983) to functions with b-bit output (b = 1 in the 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 the input. We construct families of explicit functions for which Ω(n/c^k) bits of communication are required to find the `missing bit', where n is the length of each player's input and k is the number of players. This extends the results of Babai, Nisan, Szegedy (1992). As a consequence we settle the old problem of separating the one-way vs. multiround communication complexities (in the CFL sense) for k≤(1 - ε) log n players, extending a result of Nisan and Wigderson (1991) who demonstrated this separation for k = 3 players. As a by-product we obtain Ω(n/c^k) 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 also include a previously unpublished lower bound by A. Wigderson regarding the one-way complexity of the 3-party pointer jumping function.