The Taub Faculty of Computer Science Events and Talks

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.

This is joint work with Anup Rao.