Grid-norm Regularity for Somewhat Dense Graphs, and Some Applications - Zander Kelley

Описание к видео Grid-norm Regularity for Somewhat Dense Graphs, and Some Applications - Zander Kelley

Computer Science/Discrete Mathematics Seminar II
10:30am|Simonyi 101 and Remote Access
Topic: Grid-norm Regularity for Somewhat Dense Graphs, and Some Applications
Speaker: Zander Kelley
Affiliation: Institute for Advanced Study
Date: December 13, 2024

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.

Комментарии

Информация по комментариям в разработке