Makrand Sinha: Simplified Separation of Information and Communication
Tid: On 2018-03-07 kl 12.00
Plats: ROOM 1537, Lindstedtsvägen 3, KTH
Medverkande: Makrand Sinha, University of Washington
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.