Time+Place: Monday 05/01/2015 14:30 Room Class 6, Floor 1, Taub Bld.
Title: Exponential Separation of Information and Communication
Speaker: Gillat Kol- CS-Lecture - NOTE UNUSUAL DAY AND ROOM http://www.math.ias.edu/~gkol/
Affiliation: Institute for Advanced Study (IAS), Princeton
Host: Keren Censor-Hillel

Abstract:


In profoundly influential works, Shannon and Huffman show that if Alice 
wants to send a message X to Bob, it's sufficient for her to send 
roughly H(X) bits (in expectation), where H denotes Shannon's entropy 
function. In other words, the message X can be compressed to roughly 
H(X) bits, the information content of the message. Can one prove similar 
results in the interactive setting, where Alice and Bob engage in an 
interactive communication protocol?

We show the first gap between communication complexity and information 
complexity, by giving an explicit example of a boolean function with 
information complexity O(k), and distributional communication complexity 
> 2^k. This shows that a communication protocol cannot always be 
compressed to its internal information, answering (the standard 
formulation of) the above question in the negative. By a result of 
Braverman, our example gives the largest possible gap.

By a result of Braverman and Rao, our example gives the first gap 
between communication complexity and amortized communication complexity, 
implying that strong direct sum does not hold for distributional 
communication complexity, answering a long standing open problem.

Joint work with Anat Ganor and Ran Raz.

Short Bio:

I am a postdoc fellow in the theoretical computer science group at the 
Institute for Advanced Study (IAS), Princeton. My research is in 
complexity theory. I am currently very interested in application of 
information theory to theoretical computer science, especially to 
communication complexity. Prior to joining the IAS, I completed a short 
postdoc at the Technion, received a Ph.d. and M.Sc. from the Weizmann 
Institute, and a B.A. from the Open University of Israel.