Graphical Models: Algorithms and Complexity

Probabilistic graphical models provide a very useful framework for studying several problems across theoretical computer science and statistics. Undirected graphical models have also been studied extensively in statistical mechanics under the name of "spin systems".

The first part of the talk illustrates two examples of the crucial role played by ideas from statistical mechanics in the study of several natural algorithmic problems in theoretical computer science and combinatorics via this connection to spin systems. The first connection is between a novel extension of the Lee-Yang theorem and the computational complexity of computing averages such as the mean magnetization of the Ising model and the average size of matchings. The second example illustrates the interplay between the study of the correlation decay phenomenon and the problems of approximate counting and sampling. In both cases, the algorithmic view also contributes back to the study of spin systems.

The second part of the talk considers causal inference in directed graphical models.  In particular, we study the "condition number" of the causal inference problem, and show that there are graphical models in which the problem is extremely sensitive to errors in the input. We then and propose several future directions for combating this ill-conditioning.

The results in this talk are based on collaborations with Leonard J. Schulman, Alistair Sinclair, Daniel Štefankovič, and Yitong Yin.