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


Manoj M. Prabhakaran


Indian Institute of Technology
Department of Computer Science
and Engineering
Mumbai 400076


Tuesday, 18 October 2016, 16:00 to 17:00


  • A-201 (STCS Seminar Room)


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