In this talk we will discuss some famous open problems in additive combinatorics:
- How large can a subset S of [N] be while managing to avoid k-term arithmetic progressions?
- How large can a subset S of [N]^k be while managing to avoid a k-dimensional corner? (If ⋯ represents a 3-term arithmetic progression, then ⠓ represents a 2-dimensional corner. A more formal definition will be provided in the talk, or can be found in the paper linked below.)
We will also discuss multiparty communication complexity, wherein players are given inputs and they want to compute a function of those inputs. In the Number-In-Hand model, each player can see their own input but not the inputs of others. In the Number-On-Forehead model, each player can see the other players' inputs but not their own.
In 2021 Linial and Shraibman utilized a long-known connection which showed that finding good k-party Number-On-Forehead communication protocols for the "ExactlyN" function is equivalent to finding large (k-1)-dimensional-corner-free sets. Working in the setting when k=3, they constructed an explicit protocol that matched a 1946 construction of large corner-free sets. Using the communication complexity point of view, they improved upon the protocol to create even larger sets, giving the first improvement to the "highest-order" term since 1946. This was then subsequently improved by Green later that year.
In our work we generalize this method to larger dimensions. We create explicit communication protocols that match a 1961 construction of large k-dimensional-corner-free sets. We then provide an improvement in the same vein as Linial and Shraibman and Green, giving the first improvement to the "highest-order" term since 1961.
This is joint work with Lianna Hambardzumyan, Toniann Pitassi, Morgan Shirley and Adi Shraibman. The paper can be found at https://arxiv.org/abs/2309.06554.
