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.