Abstract
In this work we introduce a new informationtheoretic complexity measure for 2party functions, called Rényi information complexity. It is a lowerbound on communication complexity, and has the two leading lowerbounds on communication complexity as its natural relaxations: (external) information complexity and logarithm of partition complexity. These two lowerbounds had so far appeared conceptually quite different from each other, but we show that they are both obtained from Rényi information complexity using two different, but natural relaxations:
1. The relaxation of Rényi information complexity that yields information complexity is to change the order of Rényi mutual information used in its definition from infinity to 1.
2. The relaxation that connects Rényi information complexity with partition complexity is to replace protocol transcripts used in the definition of Rényi information complexity with what we term "pseudotranscripts", which omits the interactive nature of a protocol, but only requires that the probability of any transcript given inputs x and y to the two parties, factorizes into two terms which depend on x and y separately. While this relaxation yields an apparently different definition than (log of) partition function, we show that the two are in fact identical. This gives us a surprising characterization of the partition bound in terms of an informationtheoretic quantity.
We also show that if both the above relaxations are simultaneously applied to Rényi information complexity, we obtain a complexity measure that is lowerbounded 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.
Further understanding Rényi information complexity (of various orders) might have consequences for important directsum problems in communication complexity, as it lies between communication complexity and information complexity.
BibTeX  Entry
@InProceedings{prabhakaran_et_al:LIPIcs:2016:6197,
author = {Manoj M. Prabhakaran and Vinod M. Prabhakaran},
title = {{R{\'e}nyi Information Complexity and an Information Theoretic Characterization of the Partition Bound}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {88:188:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6197},
URN = {urn:nbn:de:0030drops61970},
doi = {10.4230/LIPIcs.ICALP.2016.88},
annote = {Keywords: Information Complexity, Communication Complexity, R{\'e}nyi Mutual Information}
}
Keywords: 

Information Complexity, Communication Complexity, Rényi Mutual Information 
Collection: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 
Issue Date: 

2016 
Date of publication: 

23.08.2016 