HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
IMA Annual Program Year Workshop
Graphical Models, Statistical Inference, and Algorithms (GRAMSIA)
May 18-22, 2015

David GamarnikMassachusetts Institute of Technology
Andrea MontanariStanford University
Devavrat ShahMassachusetts Institute of Technology
Prasad TetaliGeorgia Institute of Technology
Rüdiger UrbankeÉcole Polytechnique Fédérale de Lausanne (EPFL)
Martin WainwrightUniversity of California, Berkeley

Graphical models are used and studied within a variety of disciplines of computer science, mathematics, and statistics. The purpose of this workshop is to highlight various mathematical 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 on applied areas, they are also connected to various branches of the mathematical sciences. Rather than focusing on the applications, the primary goal 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; given the success of this methodology, surely by 2015 the following list will have expanded to a much larger one:

  • 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.