Mathematical Challenges in Graphical Models and Message-Passing Algorithms

January 23 - 27, 2012


Graphical models are used and studied within a variety of disciplines of computer science, mathematics and statistics. The purpose of this meeting is to highlight various imagemathematical questions and issues associated with graphical models and message-passing algorithms, and to bring together a group of researchers for discussion of the latest progress and challenges ahead.

In addition to the substantial impact of graphical models in applied areas, they also are connected to various branches of the mathematical sciences. Rather than focusing on the applications, the primary goal of this meeting is to highlight and deepen these mathematical connections. Given the range of these connections, the area has great promise for growth.

More concretely, the past decade has witnessed exciting interplay between graphical models and the following branches of the mathematical sciences:

  • Probabilistic methods and combinatorics: theory of weak convergence of sparse graphs (objective method); interpolation method; techniques to establish sharp thresholds for monotone properties.
  • Statistical physics: belief propagation, cavity method, Bethe approximation, phase transitions, spatial and temporal correlation decay, mathematical methods for spin glass theory.
  • Optimization and convex relaxations: Message-passing and linear programming relaxations; variational methods and marginal polytopes.
  • Computation and theory of algorithms: Markov chain Monte Carlo algorithms; derandomization of counting algorithms; distributed computation.
  • Coding theory: random code constructions, message-passing decoding, density evolution, expander graphs.
  • Statistics and machine learning: inference in large scale data models
  • A further hope behind organizing this workshop is to seed a regular conference that will lead to the development of a rich discipline in the future.

Organizing Committee

David Gamarnik (Massachusetts Institute of Technology, Sloan School of Management)
Andrea Montanari (Stanford University)
Devavrat Shah, Chair (Massachusetts Institute of Technology)
Prasad Tetali (Georgia Institute of Technology)
Rüdiger Urbanke (EPFL (Ecole Polytechnique Fédérale de Lausanne))
Martin Wainwright (University of California, Berkeley (UC Berkeley))