Videos

Additive combinatorics through the lens of communication complexity

Presenter
November 15, 2022
Abstract
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.