Statistical Physics, Optimization, Inference, and Message-Passing Algorithms Lecture Notes of the Les Houches School of Physics: Special Issue, October 2013

In the last decade, there have been an increasing convergence of interest and methods between theoretical physics and fields as diverse as probability, machine learning, optimization and compressed sensing. In particular, many theoretical and applied works in statistical physics and computer science have relied on the use of message passing algorithms and their connection to statistical physics of spin glasses. The aim of this book, especially adapted to PhD students, post-docs, and young researchers, is to present the background necessary for entering this fast developing field.

1 - Statistical inference with probablistic graphical moddels
2 - Computational Complexity, Phase Transitions, and Message-Passing for Community Detection
3 - Replica Theory and Spin Glasses
4 - Cavity method: message passing from a physics perspective
5 - Statistical Estimation: From Dnoising to Sparse Regression and Hidden Cliques
6 - Error correcting codes and spatial coupling
7 - Contraint satisfaction - Random regular k-SAT
8 - Local Algorithms for Graphs
9 - Expectation Propagation
10 - A cavity approach to optimisation and inverse dynamical problems

Florent Krzakala is a Professor in physics at Université Pierre et Marie in Paris, France, and is doing his research in Ecole Normale Supérieure on statistical physics and disordered systems. Currently, he is leading a research team working on the development of interdisciplinary methods between statistical physics and computer science. Federico Ricci-Tersenghi is Associate Professor at the University of Rome La Sapienza, Italy. He his the co-author of "Scientific Programming: C-Language, Algorithms and Models in Science". He has an interest in the statistical physics of disordered systems, such as spin glasses, glasses, networks, optimization problems, inference and learning. Eric W. Tramel is a postdoctoral research fellow at Ecole Normale Supérieure in Paris, France, researching the interface between statistical physics and signal processing from the perspective of electrical computer engineering. Riccardo Zecchina is a professor at the Politecnico di Torino, Italy. His research interest lies at the interface between statistical physics, computer science, information theory and computational biology. Curently, he us engaged in applying the statistical physics techniques to inverse problems that arise in computational biology and neuroscience. Lenka Zdeborová is a researcher in the Institute for Theoretical Physics (IPhT) of the Centre National de la Recherche Scientifique in Saclay, France. Her main research interest are applications of methods from statistical mechanics and theoretical physics to problems in computer science, information theory, signal processing and machine learning. She was recently awarded the CNRS bronze medal for her work on statistical physics and computer science.; Leticia F. Cugliandolo is Professor at the Laboratoire de Physique Theorique et Hautes Energies Universite Pierre et Marie Curie, Paris, France. She is the director of the Les Houches School of Physics.