Text only print
Full screen print
Lectures
Seminar information archive ～04/18｜Next seminar｜Future seminars 04/19～
2011/03/22
14:00-15:00 Room #128 (Graduate School of Math. Sci. Bldg.)
Amir Dembo (Stanford Univ.)
Potts models and Bethe states on sparse random graphs (JAPANESE)
Amir Dembo (Stanford Univ.)
Potts models and Bethe states on sparse random graphs (JAPANESE)
[ Abstract ]
Theoretical models of disordered materials lead to challenging mathematical problems with applications to random combinatorial problems and coding theory. The underlying mathematical structure is that of many discrete variables that are strongly interacting according to a mean field model determined by a random sparse graph. Focusing on ferromagnetic Potts measures on random finite graphs that converge locally to trees we validate the `cavity' prediction for the limiting free energy per spin and show that local marginals are approximated well by the belief propagation algorithm. This is a concrete example of the more general approximation by Bethe measures, namely, the local convergence of the Boltzmann distribution on the original graph to the Boltzmann distribution on an appropriate infinite random tree (this talk is based on a joint work with Andrea Montanari and Nike Sun).
Theoretical models of disordered materials lead to challenging mathematical problems with applications to random combinatorial problems and coding theory. The underlying mathematical structure is that of many discrete variables that are strongly interacting according to a mean field model determined by a random sparse graph. Focusing on ferromagnetic Potts measures on random finite graphs that converge locally to trees we validate the `cavity' prediction for the limiting free energy per spin and show that local marginals are approximated well by the belief propagation algorithm. This is a concrete example of the more general approximation by Bethe measures, namely, the local convergence of the Boltzmann distribution on the original graph to the Boltzmann distribution on an appropriate infinite random tree (this talk is based on a joint work with Andrea Montanari and Nike Sun).
