On the Complexity of Communication Complexity

We consider the following question: given a two-argument boolean function f. represented its an N x N binary matrix. how hard is it to determine the (deterministic) communication complexity of f? We address two aspects of this question. On the computational side, we prove that, under appropriate cryptographic assumptions (Such as the intractability of factoring), the deterministic communication complexity of f is hard to approximate to within some constant. Under stronger (yet arguably reasonable) assumptions, we obtain even stronger hardness results that match file best known approximation. On the analytic side we present a family of (two-argument functions for which determining the deterministic communication complexity (or even obtaining non-trivial lower bounds on it) implies proving circuit lower bounds for some related functions. Such connections between Circuit complexity and communication complexity were known before (Karchmer & Wigderson, 1988) only in the more involved context of relations (search problems) but not ill the context of functions (decision problems). This result, ill particular. may explain the difficulty of analyzing the communication complexity of certain functions Such as the "clique vs. independent-set" family Of functions. introduced by Yannakakis (1988).