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

Friday, February 28, 2014 - 1:45pm
Pizza at 12:30pm
MSR New England (Barton room on the 1st floor of One Memorial Drive building)
Emmanuel Abbe

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.