Printable PDF
Department of Mathematics,
Department of Mathematics,
University of California San Diego
****************************
Math 269: Combinatorics Seminar
Anthony Ostuni
UC San Diego
Corners and Communication Complexity
Abstract:
We will discuss recent progress on the corners problem from additive combinatorics and its connection to communication complexity. In particular, we will sketch a proof that every set $A \subseteq [N]^2$ of density $\gg exp(- polylog N)$ must contain three points of the form $(x,y)$, $(x+d,y)$, $(x,y+d)$ for some nonzero $d$. We will also show how this result implies strong lower bounds for the multiparty communication complexity of the Exactly-$N$ function.
Based on joint work with Michael Jaber, Yang P. Liu, Shachar Lovett, and Mehtaab Sawhney.
March 3, 2026
2:00 PM
APM 7321
Research Areas
Combinatorics****************************
