We introduce a new information-theoretic complexity measure IC∞ for 2-party functions which is a lower-bound on communication complexity, and has the two leading lower-bounds on communication complexity as its natural relaxations: (external) information complexity (IC) and logarithm of partition complexity (prt). These two lower-bounds had so far appeared conceptually quite different from each other, but we show that they are both obtained from IC∞ using two different, but natural relaxations:

• IC∞ is similar to information complexity IC, except that it uses Rényi mutual information of order ∞ instead of Shannon's mutual information (which is Rényi mutual information of order 1). Hence, the relaxation of IC∞ that yields IC is to change the order of Rényi mutual information used in its definition from ∞ to 1.

• The relaxation that connects IC∞ with partition complexity is to replace protocol transcripts used in the definition of IC∞ with what we term “pseudotranscripts,” which omits the interactive nature of a protocol, but only requires that the probability of any transcript given inputs x and y to the two parties, factorizes into two terms which depend on x and y separately. While this relaxation yields an apparently different definition than (log of) partition function, we show that the two are in fact identical. This gives us a surprising characterization of the partition bound in terms of an information-theoretic quantity.

Further understanding IC∞ might have consequences for important direct-sum problems in communication complexity, as it lies between communication complexity and information complexity.

We also show that if both the above relaxations are simultaneously applied to IC∞, we obtain a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by Kerenidis et al. (FOCS 2012). We obtain a similar (but incomparable) connection between (external) information complexity and relaxed partition complexity as Kerenidis et al., using an arguably more direct proof.

This is joint work with Vinod Prabhakaran.