Abstract
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.