The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science
 
                    Foundations of Computer Science Seminar
 
                     Lecture Hall, Room 1, Ziskind Building
                           on Sunday, April 14, 2013
                                    at 11:00
 
                          PLEASE NOTE UNUSUAL DAY/TIME
 
                                   David Xiao
                          University of Paris-Diderot
 
                                 will speak on
 
              Some optimal lower bounds for information complexity
 
Abstract:
In a two-party communication games, two players Alice and Bob each hold some
input $x$ and $y$ respectively, and wish to compute some function $f(x, y)$ by
communicating interactively.  The traditional measure of complexity in this
model is the number of bits that Alice and Bob must transmit in order to
correctly compute $f$.  More recently, researchers have become interested in
the information complexity of protocols: how much information about $x$ and $y$
does the transcript reveal?
 
In this talk I will discuss some optimal lower bounds on information complexity
for various functions, including Disjointness and Inner Product.  Our results
state, roughly, that almost all known lower bounds on communication complexity
in fact also give lower bounds on information complexity.  Surprisingly, even
though our theorems are for classical communication, some of our main
techniques were first developed to study quantum phenomena.
 
As corollaries to our main theorems, we obtain direct sum theorems for
essentially all functions whose communication complexities are known, and we
also obtain an exponential separation between classical information and quantum
one-way communication.
 
Based on joint works with Iordanis Kerenidis, Sophie Laplante, Mathieu
Lauriere, Virginie Lerays, and Jeremie Roland.
 
---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Gizel Maimon   <gizel.maimon@weizmann.ac.il>