Princeton University

School of Engineering & Applied Science

Information Complexity Density and Simulation of Protocols

Pramod Viswanath, University of Illinois, Urbana-Champaign
E-Quad, B205
Thursday, May 7, 2015 - 4:30pm to 5:30pm

Abstract: Two parties observing random inputs use interactive communication to produce a desired output to within a fixed statistical distance \eps. A fundamental quantity is the distributional communication complexity of the protocol, the minimum number of bits that the parties for a successful simulation. Recent works have proposed the information complexity as the central quantity governing the distributed communication complexity of the protocol, and designed several simulation protocols correspondingly. However, in the absence of any general lower bounds for distributional communication complexity, the central role of information complexity is far from settled. We show that the \eps-tail of the information complexity density, a random variable with information complexity as its expected value is a stronger lower bound to the distributional communication complexity, and is tight in many scenarios of interest. Applications include the exact second order term, together with the precise dependence on \eps for the amortized regime. In the single-shot regime, the distinguishing feature of our lower bound is that it clarifies the dependence of communication complexity on \eps.
Bio: Pramod Viswanath received the PhD degree in EECS from the University of California at Berkeley in 2000. He was a member of technical staff at Flarion Technologies until August 2001 before joining the ECE department at the University of Illinois, Urbana-Champaign. He is a recipient of the Xerox Award for Faculty Research from the College of Engineering at UIUC (2010), the Eliahu Jury Award from the EECS department of UC Berkeley (2000), the Bernard Friedman Award from the Mathematics department of UC Berkeley (2000), and the NSF CAREER Award (2003). He was an associate editor of the IEEE Transactions on Information Theory for the period 2006-2008.