The Cost of the Missing Bit: Communication Complexity with Help

详细信息    查看全文

• 作者：L¨¢szl¨® Babai ; Thomas P. Hayes and Peter G. Kimmel
• 关键词：AMS Subject Classification (2000) Classes ;   ; 68Q05 ; 11K38 ; 68R05 ; 03D15 ; 94A99
• 刊名：Combinatorica
• 出版年：2001
• 出版时间：October 2001
• 年：2001
• 卷：21
• 期：4
• 页码：455-488
• 全文大小：401 KB

文摘

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.