Marston Morse Lectures

(This lecture is related to the preceding lecture, but I will try to make it self-contained as much as possible.) In this lecture I will elaborate on some of the existing mathematical approaches to the study of random CSPs, particularly involving the (first and second) moment method. We will see that implementing the moment method often reduces to the solution of difficult (non-convex) optimization problems. I will discuss one basic strategy that has been used to solve some of these problems, which is to (1) use a priori estimates to localize the optimization to a small neighborhood, and (2) use the contractivity of tree recursions and a "local update" procedure to solve the optimization within the small neighborhood.

This lecture is based in part on joint works with Zsolt Bartha, Jian Ding, Allan Sly, and Yumeng Zhang.