Hastad showed that 3SAT has a sharp approximation threshold of 7/8 on satisfiable instances. Specifically, given a satisfiable instance of 3SAT, one can algorithmically find an assignment that satisfies 7/8 fraction of the clauses and it is NP-hard to do strictly better.

This talk will give an overview of our continued effort towards characterizing such a sharp threshold for every satisfiable constraint satisfaction problem (CSP). Our results so far include: a hybrid algorithm that combines semi-definite programming and Gaussian elimination over an Abelian group and is (arguably) optimal for some CSPs; progress on some questions in additive combinatorics, in particular, the Density Hales-Jewett theorem; progress on the 3-player parallel repetition theorem; and progress on some questions in property testing.

At the heart of these results lies progress on an analytic question, namely, understanding expectations of the type

E [f(x) f(y) f(z)] where x,y,z are correlated inputs from a product space and f is a bounded function.

Based on joint works, mostly with Amey Bhangale, Dor Minzer, Yang P. Liu, and some with Mark Braverman.