Phase transitions and efficient algorithms
(Uni Frankfurt)Thursday 20 June 2013, 15.00, b-it 1.25 (cosec meeting room)
Phase transitions have long been studied in statistical mechanics. Over the years, physicists have developed ingenious, albeit non-rigorous techniques for the study of phase transitions. In recent years it has emerged that phase transitions also have an impact on the performance of algorithms. In this talk I am going to give an overview of this. In addition, I am going to survey the recent progress in turning the statistical mechanics work into a rigorous theory.