Speaker
Andrea Montanari
(Stanford)
Description
A substantial amount of mathematical work has been devoted to studying structural
properties of mean-field spin glasses, and in particular, geometric properties of the Gibbs measure. Over the last ten years, ideas from spin glass theory have spurred dramatic advances in the field of random combinatorial optimization and random constraint satisfaction problems (CSPs), allowing to characterize some key structural properties of the latter (eg the satisfiability threshold in random CSPs). Can spin glass ideas also lead to the construction of efficient algorithms for these problems?
I will describe recent progress on the last question.
