Lower bounds on information complexity via zero-communication protocols and applications: Virginie Lerays, Universite Paris

Starts:
2:00 pm on Friday, October 26, 2012
Ends:
4:00 pm on Friday, October 26, 2012
Location:
MCS 148
Abstract: The information complexity of a protocol is a lower bound on its communication complexity. One open question is whether these quantities are equal or not. We show that almost all known lower bound methods for communication complexity are also lower bounds for information complexity. To do that, we define a relaxed version of the partition bound of Jain and Klauck, which subsumes all rectangle and norm-based techniques, and we show that it lower bounds the information complexity. Our result uses a recent connection between rectangle techniques and zero-communication protocols where players can abort (Laplante,Lerays, Roland 2012). More precisely, the maximum achievable probability that the protocol doesn't abort, which is called efficiency, gives a lower bound on communication complexity which corresponds to the relaxed partition bound. We use compression techniques to relate IC to efficiency. In this talk, I will first make the link between zero communication protocols, communication complexity and rectangle techniques and then present the compression technique which is similar to those of Braverman and Weinstein 2012 and Braverman 2012. Finally I will present some applications of our theorem.