We introduce a new information-theoretic complexity measure @math 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 ( @math ) and logarithm of partition complexity ( @math ), which have so far appeared conceptually quite different from each other. @math is an external information complexity measure based on R 'enyi mutual information of order infinity. In the definition of @math , relaxing the order of R 'enyi mutual information from infinity to 1 yields @math , while @math 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 @math and @math to the two parties, factorizes into two terms which depend on @math and @math separately. Further understanding @math 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 @math gives a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by (FOCS 2012). We obtain a sharper connection between (external) information complexity and relaxed partition complexity than , using an arguably more direct proof.
Recently, the authors of this work proposed a distributional complexity measure, Wyner tension (or more generally, tension gap) which is a lower bound for information complexity @cite_24 . We leave it for future work to explore the exact connections between these bounds and the ones in the current work. We mention that for the case when the inputs are independent, Wyner tension is identical to (defined in extensions ), and a result in @cite_24 is subsumed by the results in this work.
@cite_24
1793958621
The main contribution of this work is to relate information complexity to "tension" [Prabhakaran and Prabhakaran, 2014] - an information-theoretic quantity defined with no reference to protocols - and to illustrate that it allows deriving strong lower-bounds on information complexity. In particular, we use a very special case of this connection to give a quantitatively tighter connection between information complexity and discrepancy than the one in the work of Braverman and Weinstein (2012) (albeit, restricted to independent inputs). Further, as tension is in fact a multi-dimensional notion, it enables us to bound the 2-dimensional region that represents the trade-off between the amounts of communication in the two directions in a 2-party protocol. This work is also intended to highlight tension as a fundamental measure of correlation between a pair of random variables, with rich connections to a variety of questions in computer science and information theory.