The cost of the missing bit
László Babai, Thomas P. Hayes, Peter G. Kimmel · 1998
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,