• Calendar

December 9, Tuesday
12:00 – 14:00

We survey lower bound techniques in communication complexity. Lower bounds in communication complexity can be roughly divided into two groups. One group uses information theoretic principles and the other uses geometric tools. We focus on the later family of lower bounds. A partial list of the geometric tools that are used is: Fourier analysis, singular values, operator norms, factorization norms and approximation theory. But perhaps the strongest tool, which in a way ties everything together, is duality. Duality and its role in proving lower bounds in communication complexity will be a main subject of our talk. Although we discuss applications to communication complexity, the techniques we present can be used in a much more general settings. We will mention connections to learning theory and circuit complexity.

The talk is self-contained, no prior knowledge is assumed.