The Cost of the Missing Bit: Communication Complexity with Help.
László Babai, Thomas P. Hayes, Peter Kimmel.
Combinatorica 21 (4) (2001) 455-488.
Preliminary version in:
Proc. 30th Annual ACM Symposium on Theory of Computing (STOC 1998) 673--682.
Dedicated to the Memory of Paul Erdős
Abstract:
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
Ω(n/ck)
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 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/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 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.