Computer Science/Discrete Mathematics Seminar II

In this talk I will first review some basics about communication complexity.  Secondly I will survey some (old and new) equivalences between central problems in communication complexity and related questions in additive combinatorics.  In particular, we will reformulate a few questions in additive combinatorics (Arithmetic Progressions, Corners Theorem, Hales-Jewitt Theorem, and dense Ruzsa-Szemeredi graphs) as equivalent questions in communication complexity. I will then discuss some recent progress on the Corners problem, based on this connection.