A comparison of two lower-bound methods for communication complexity

AbstractThe methods “Rank” and “Fooling Set” for proving lower bounds on the deterministic communication complexity of Boolean functions are compared. The main results are as follows. 1.(i) For almost all Boolean functions of 2n variables the Rank method provides the lower bound n on communication complexity, whereas the Fooling Set method provides only the lower bound d(n) ⩽ log2 n + log2 10. A specific sequence {ƒ2n}n = 1∞ of Boolean functions, where ƒ2n has 2n variables, is constructed such that the Rank method provides exponentially higher lower bounds for ƒ2n than the Fooling Set method.2.(ii) A specific sequence {h2n}n = 1∞ of Boolean functions is constructed such that the Fooling Set method provides a lower bound of n for h2n, whereas the Rank method provides only (log2 3)2 · n ≈ 0.79 · n as a lower bound.3.(iii) It is proved that lower bounds obtained by the Fooling Set method are better by at most a factor of two compared with lower bounds obtained by the Rank method. These three results together solve the last problem about the comparison of lower bound methods on communication complexity left open in Aho et al. (1983).Finally, it is shown that an extension of the Fooling Set method provides lower bounds that are tight (up to a polynomial) for all Boolean functions