[Busec] Fwd: Theory Seminar Friday, 10/26 at 2:00, Virginie Lerays on Communication Complexity

Leonid Reyzin 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
Communication Complexity
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
and applications.


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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20121024/05b17a11/attachment.html>

More information about the Busec mailing list