The Taub Faculty of Computer Science Events and Talks

We consider the following question: given a two-argument boolean function $f$, represented as an $N\times N$ binary matrix, how hard is 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 obtains even stronger hardness results that match the best known approximation.

On the analytic side, we present a family of functions for which determining the communication complexity (or even obtaining non-trivial lower bounds on it) imply proving circuit lower bounds for some corresponding problems. Such connections between circuit complexity and communication complexity were known before (Karchmer-Wigderson 1988) only in the more involved context of relations (search problems) and not in the context of functions (decision problems). This result, in 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). Joint work with Eyal Kushilevitz