Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: How to Compress Asymmetric Communication
event speaker icon
Sivaramakrishnan Natarajan Ramamoorthy (University of Washington)
event date icon
Wednesday, 18.11.2015, 12:30
event location icon
Taub 201
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.