IC Colloquium: Partition Functions: What they are and how to compute them
By: Alistair Sinclair - UC Berkeley
Video of his talk
Abstract
A partition function is a polynomial whose coefficients carry information about the possible configurations of a system or model. Partition functions are ubiquitous in physics, combinatorics, probability, theoretical computer science and machine learning. In almost all interesting cases, computing a partition function exactly is an intractable problem, but several techniques exist for approximating them. This talk will outline three main techniques—Markov chain Monte Carlo, correlation decay and complex analysis—and indicate when they are applicable. I will also briefly discuss the connection between computational complexity of partition functions and phase transitions in the underlying model.
Bio
Alistair Sinclair received his BA in Mathematics from the University of Cambridge in 1982, and his PhD in Computer Science from the University of Edinburgh in 1988. After a period on the faculty at Edinburgh, he moved to UC Berkeley in 1994, where he is now the Kikuo Ogawa and Kaoru Ogawa Professor of Computer Science. He has held visiting positions at DIMACS, Princeton University, Rutgers University, Microsoft Research, Ecole Polytechnique, University of Paris-Orsay, and University of Rome III. He was a winner of the 1996 Gödel Prize and the 2006 Fulkerson Prize, is an ACM Fellow, and was an IMS Medallion Lecturer. He also received the SIGACT Distinguished Service Prize for his role in establishing and running the Simons Institute for the Theory of Computing from 2012-17. Sinclair’s research interests focus on various applications of randomness in computer science, including randomized algorithms and Markov chain Monte Carlo, as well as on topics at the intersection of computer science and statistical physics.
More information
Video of his talk
Abstract
A partition function is a polynomial whose coefficients carry information about the possible configurations of a system or model. Partition functions are ubiquitous in physics, combinatorics, probability, theoretical computer science and machine learning. In almost all interesting cases, computing a partition function exactly is an intractable problem, but several techniques exist for approximating them. This talk will outline three main techniques—Markov chain Monte Carlo, correlation decay and complex analysis—and indicate when they are applicable. I will also briefly discuss the connection between computational complexity of partition functions and phase transitions in the underlying model.
Bio
Alistair Sinclair received his BA in Mathematics from the University of Cambridge in 1982, and his PhD in Computer Science from the University of Edinburgh in 1988. After a period on the faculty at Edinburgh, he moved to UC Berkeley in 1994, where he is now the Kikuo Ogawa and Kaoru Ogawa Professor of Computer Science. He has held visiting positions at DIMACS, Princeton University, Rutgers University, Microsoft Research, Ecole Polytechnique, University of Paris-Orsay, and University of Rome III. He was a winner of the 1996 Gödel Prize and the 2006 Fulkerson Prize, is an ACM Fellow, and was an IMS Medallion Lecturer. He also received the SIGACT Distinguished Service Prize for his role in establishing and running the Simons Institute for the Theory of Computing from 2012-17. Sinclair’s research interests focus on various applications of randomness in computer science, including randomized algorithms and Markov chain Monte Carlo, as well as on topics at the intersection of computer science and statistical physics.
More information
Practical information
- General public
- Free
Contact
- Host: Rüdiger Urbanke