Computer Science/Discrete Mathematics Seminar II
Grid-norm Regularity for Somewhat Dense Graphs, and Some Applications
In 2023, Raghu Meka and I proved a substantially improved bound on the size of the smallest set of integers in [N] which contains no 3-term arithmetic progression. Since then, it has become clear that the main new ideas from that work are in fact best thought of as generic graph-theoretic tools (rather than being limited to the study of arithmetic structures). There have since been a number of new applications (for example, in communication complexity and graph algorithms) which rely on and refine these graph-theoretic tools.
In this talk, I will discuss some of these applications, and present a summary of the new graph-theoretic tools powering them. In particular, I will discuss the grid-norm, a key definition which is useful for measuring the pseudorandomness of a bipartite graph.
Based on joint works with Amir Abboud, Nick Fischer, Shachar Lovett and Raghu Meka.