The ACO Seminar (2025–2026)

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,\dots,f_k$ have nonnegligible correlation over a product distribution $\mu^n$, what structure can one deduce about the functions $f_1,\dots,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.