Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound

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:

* 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 of IC∞ that yields log prt 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.

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).