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.

Date & Time

November 15, 2022 | 10:30am – 12:30pm

Location

Simonyi Hall 101 and Remote Access

Affiliation

University of Toronto and Columbia University; Visiting Professor, School of Mathematics