English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We introduce a new information-theoretic complexity measure $IC_\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. $IC_\infty$ is an external information complexity measure based on R\'enyi mutual information of order infinity. In the definition of $IC_\infty$, relaxing the order of R\'enyi 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 $IC_\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 $IC_\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.

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