Markov chain Monte Carlo based on message passing (LTHC)

 Description and objectives:

In this project we want to investigate new types of Markov chain Monte Carlo algorithms for large probabilistic graphical models, where the update rules of the Markov chain are based on a message passing calculation in a limited neighborhood of the nodes. Such ideas generalize the so-called Glauber or heat bath dynamics. They can be applied to random combinatorial optimization problems such as coloring random graphs or constraint satisfaction on sparse graphs, or matrix factorization, estimation problems on dense graphs.

Aspects of the work will have to do with the numerical implementation of such ideas and an empirical study of their applicability. Bounds on mixing times can investigated by semi-analytical methods.

Prerequisite:

Familiarity with Markov chains, stochastic processes, having taken a class on these topics.

Lab and supervisor:

Nicolas Macris (for more information please contact me)

Number of students: one student