[Busec] Fwd: Theory Seminar Friday, 10/26 at 2:00, Virginie Lerays on Communication Complexity
reyzin at cs.bu.edu
Wed Oct 24 11:56:01 EDT 2012
A theory talk of interest to BUSec:
---------- Forwarded message ----------
From: Steve Homer <homer at cs.bu.edu>
Date: Mon, Oct 22, 2012 at 3:11 PM
Subject: Theory Seminar Friday, 10/26 at 2:00, Virginie Lerays on
To: Steve Homer <homer at cs.bu.edu>
BU Friday Theory Talk
Virginie Lerays (Universite Paris)
Friday, October 26, 2012 at 2:00
Room MCS 148 of 111 Cummington Street
Lower bounds on information complexity via zero-communication protocols
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
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Busec