Makrand Sinha: Simplified Separation of Information and Communication

PRACTICALITIES
Lunch is served at 12:00 noon (register at goo.gl/YNBEbx  at the latest on Monday March 5, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

ABSTRACT
We give an example of a boolean function whose information complexity is exponentially smaller than its communication complexity. This was first proven recently by Ganor, Kol and Raz (J. ACM ‘16) and our work gives a simpler proof of the same result. In the course of this simplification, we make several new contributions: we introduce a new communication lower bound technique, the notion of a fooling distribution, which allows us to separate information and communication complexity, and we also give a more direct proof of the information complexity upper bound. We also prove a generalization of Shearer’s Lemma that may be of independent interest. This is joint work with Anup Rao.