Emmanuel Abbe: Concentration Results in Random CSPs , Soft CSPs and Applications

I will start with an overview of the basic phase transition and concentration results for random k-SAT, and discuss more recent results for planted k-SAT. I will then discuss "soft CSPs", where the constraints are not hard but probabilistic, and where the goal is not to decide satisfiability but to quantify the likelihood of solutions. Applications to coding theory and graph clustering will be discussed, as well as proof techniques, in particular the interpolation method.