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

Manoj M. Prabhakaran, Vinod M. Prabhakaran

We introduce a new information-theoretic complexity measure $I{C}_{\infty }$ for 2-party functions which is a lower-bound on communication complexity, and has the two leading lower-boun…