Tata Institute of Fundamental Research
Graphical Models: Algorithms and Complexity
STCS Seminar
Speaker:
Piyush Srivastava (California Institute of Technology
Department of Computing and
Mathematical Sciences
1200 E. California Blvd.
Pasadena, CA 91125
United States of America)
Organiser:
Jaikumar Radhakrishnan
Date:
Friday, 22 Jan 2016, 11:30 to 12:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: 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.
| Speaker: | Piyush Srivastava (California Institute of Technology Department of Computing and Mathematical Sciences 1200 E. California Blvd. Pasadena, CA 91125 United States of America) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Friday, 22 Jan 2016, 11:30 to 12:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: 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.
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.