Information Complexity Lower Bounds in Communication Complexity

I will describe the information-complexity approach to proving lower bounds in communication complexity. This technique, developed by Bar-Yossef, Jayram, Kumar, and Sivakumar, gives a lower bound on the amount of information that a protocol must "leak" to an observer about the inputs, and using this bound obtains a lower bound on the communication complexity of the problem. I will start by reviewing basic concepts in information theory, and prove an Omega(n) lower bound on the information complexity of two-player set disjointness. Time permitting, I will then present a recent extension of information complexity to message-passing models, which yields a tight bound of Omega(nk) on the complexity of set disjointness with k players who communicate by sending private messages to each other. The message-passing model has previously received little interest from the communication complexity community, but we believe it has exciting applications in distributed computing and cryptography.