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>