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

Abstract

We introduce a new information-theoretic complexity measure $I{C}_{\infty }$ 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 ($\text{prt}$), which have so far appeared conceptually quite different from each other. $I{C}_{\infty }$ is an external information complexity measure based on Rényi mutual information of order infinity. In the definition of $I{C}_{\infty }$, relaxing the order of Rényi mutual information from infinity to 1 yields $IC$, while $\log \text{prt}$ is obtained by replacing protocol transcripts with what we term "pseudotranscripts," which omits the interactive nature of a protocol, but only requires that the probability of any transcript given the inputs $x$ and $y$ to the two parties, factorizes into two terms which depend on $x$ and $y$ separately. Further understanding $I{C}_{\infty }$ might have consequences for important direct-sum problems in communication complexity, as it lies between communication complexity and information complexity. We also show that applying both the above relaxations simultaneously to $I{C}_{\infty }$ gives 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 sharper connection between (external) information complexity and relaxed partition complexity than Kerenidis et al., using an arguably more direct proof.

Full version of paper appearing at ICALP 2016

References in corpus (5)

• Lower bounds on information complexity via zero-communication protocols and applications
• A direct sum theorem in communication complexity via message compression
• Information Equals Amortized Communication
• Tension Bounds for Information Complexity
• Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming