CSP Inverse Theorems and Additive Combinatorics

SEMINARS: HARVARD-MIT COMBINATORICS

When: March 7, 2025
4:15 pm - 5:15 pm
Where: MIT, Room 2-361
Address: 182 Memorial Dr, Cambridge, MA 02139, United States
Speaker: Yang P. Liu (Carnegie Mellon University)

A recent line of work initiated by Bhangale-Khot-Minzer to study the approximability of satisfiable CSPs sought to understand the following problem: if functions f_1, …, f_k have nonnegligible correlation over a product distribution \mu^n, what structure can one deduce about the functions f_1, …, f_k?

In this talk, we discuss a recent result which answers this question for k = 3 for a natural class of “pairwise-connected” distributions \mu, building upon previous results. Additionally, we discuss applications of this result to property testing and additive combinatorics. Of particular note is the first “reasonable” bound for the density Hales-Jewett problem for combinatorial lines of length three.

Based on joint work with Amey Bhangale, Subhash Khot, and Dor Minzer.

For information about the Richard P. Stanley Seminar in Combinatorics, visit https://math.mit.edu/combin/