Spring 2015

How to Compress Asymmetric Communication

Friday, Apr. 24, 2015 2:30 pm3:00 pm

Add to Calendar


Calvin Lab Auditorium

We study the relationship between communication and information in 2-party communication protocols when the information is asymmetric. If I_A denotes the number of bits of information revealed by the first party, I_B denotes the information revealed by the second party, and C is the number of bits of communication in the protocol, we show that 

-- one can simulate the protocol using order  I_A + C^{3/4} I_B^{1/4} log C  bits of communication,
-- one can simulate the protocol using order I_A  2^{O(I_B)} bits of communication

The first result gives the best known bound on the complexity of a simulation when I_A >> I_B ,C^{3/4}. The second gives the best known bound when I_B << log C. In addition we show that if a function is computed by a protocol with asymmetric information complexity, then the inputs must have a large, nearly monochromatic rectangle of the right dimensions, a fact that is useful for proving lower bounds on lopsided communication problems.

This is joint work with Anup Rao.

File simonscopy.key2.23 MB