2015/11/25 by Manoj Prabhakaran, Prabhakaran, Manoj M., Vinod M. Prabhakaran +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1511.07949
openalex publication_date 2015/11/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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), which have so far appeared conceptually quite different from each other. IC_∞ is an external information complexity measure based on Rényi mutual information of order infinity. In the definition of IC_∞, relaxing the order of Rényi mutual information from infinity to 1 yields IC, while log 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_∞ 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_∞ 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.