Login
Talks & Seminars
Title: Spin Systems and Graphical Models: Algorithms and Complexity
Dr. Piyush Srivastava, California Institute of Technology
Date & Time: January 18, 2016 11:30
Venue: Conference Room, C Block, 01st Floor, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
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 also 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 Profile:
Piyush Srivastava is currently a post-doctoral scholar at the Center for the Mathematics of Information, California Institute of Technology. He received his PhD from the University of Cailfornia, Berkeley in 2014. He received a B. Tech. in CSE from IIT Kanpur in 2009, receiving the President's Gold Medal. He was ranked first in JEE 2005.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback