Rényi information complexity and an information theoretic characterization of the partition bound

DOI10.4230/LIPICS.ICALP.2016.88MaRDI QIDQ4598228zbMATH OpenOpenAlexFDO

Authors Manoj Prabhakaran, Vinod M. Prabhakaran

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1511.07949

zbMATH Keywords

communication complexityinformation complexityRényi mutual information

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Measures of information, entropy (94A17)

Abstract: We introduce a new information-theoretic complexity measure $I{C}_{i}nfty$ 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 ($extprt$), which have so far appeared conceptually quite different from each other. $I{C}_{i}nfty$ is an external information complexity measure based on R'enyi mutual information of order infinity. In the definition of $I{C}_{i}nfty$, relaxing the order of R'enyi mutual information from infinity to 1 yields $IC$, while $logextprt$ 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}_{i}nfty$ 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}_{i}nfty$ 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.

Recommendations

• Lower bounds on information complexity via zero-communication protocols and applications
• Relative discrepancy does not separate information and communication complexity
• Relative discrepancy does not separate information and communication complexity
• Randomized communication versus partition number

Cited in

(6)

• Lower bounds on information complexity via zero-communication protocols and applications
• On Exact and ∞-Rényi Common Informations
• An information-theoretic characterization of partitioned property spaces
• Bounds on shannon distinguishability in terms of partitioned measures
• A hierarchy of constant communication complexity
• The relative growth of information in two-dimensional partitions

This page was built for publication: Rényi information complexity and an information theoretic characterization of the partition bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598228)