Theoretical Physics Colloquium

Phase transitions and computational complexity theory

by Prof. Piyush Srivastava (TIFR, Mumbai)

Tuesday, September 5, 2017 from to (Asia/Kolkata)
at AG 69
Description
This talk will survey some developments in the past decade establishing very tight connections between various classical notions of phase transitions in statistical mechanics and computational complexity theory. One of the first examples of this was the fact that the uniqueness phase transition on the Bethe lattice of a given degree exactly determines the computational complexity of the problems of computing the partition function and sampling from the Gibbs distribution of the hard core lattice gas and the anti-ferromagnetic Ising model on graphs of the same degree. We will also survey some more recent work on applications of the Lee-Yang theory of phase transitions to algorithms.

References:

a) Weitz, Dror. 2006. “Counting Independent Sets Up to the Tree Threshold.” In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, 140–149. STOC ’06. New York, NY, USA: ACM. Available from http://dimacs.rutgers.edu/~dror/pubs/ind_from_tree.pdf

b) Sinclair, Alistair, Piyush Srivastava, and Marc Thurley. 2014. “Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs.” Journal of Statistical Physics 155 (4): 666–86.
http://dx.doi.org/10.1007/s10955-014-0947-5

c) Sly, Allan, and Nike Sun. 2014. “Counting in Two-Spin Models on d-Regular Graphs.” The Annals of Probability 42 (6): 2383–2416. http://dx.doi.org/10.1214/13-AOP888

d) Sinclair, Alistair, and Piyush Srivastava. 2014. “Lee–Yang Theorems and
the Complexity of Computing Averages.” Communications in Mathematical Physics 329 (3): 827–58. http://dx.doi.org/10.1007/s00220-014-2036-7. 

e) Barvinok, Alexander. 2015. “Computing the Permanent of (Some) Complex 
Matrices.” Foundations of Computational Mathematics 16 (2): 329–42.
http://dx.doi.org/10.1007/s10208-014-9243-7

f) Patel, Viresh, and Guus Regts. 2016. “Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials.” arXiv:1607.01167 [Cs,Math]. http://arxiv.org/abs/1607.01167

g) Liu, Jingcheng, Alistair Sinclair, and Piyush Srivastava. 2017. “The Ising Partition Function: Zeros and Deterministic Approximation.”
arXiv:1704.06493 [Cond-Mat]. http://arxiv.org/abs/1704.06493