The Cost of the Missing Bit: Communication Complexity with Help

Dedicated to the Memory of Paul Erdős 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 players to receive up to b - 1 bits of information from an all-powerful 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 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. As a consequence we settle the problem of separating the one-way vs. multiround communication complexities (in the CFL sense) for players, extending a result of Nisan and Wigderson (1991) who demonstrated this separation for k = 3 players. As a by-product we obtain 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 concepts of multicolor discrepancy; discrete Fourier analysis is the basic tool. We also include an unpublished lower bound by A. Wigderson regarding the one-way complexity of the 3-party pointer jumping function. Received November 12, 1998 RID="*" ID="*" Supported in part by NSA grant MSPR-96G-184. RID="†" ID="†" Supported in part by an NSF Graduate Fellowship.