Spin Systems: Hardness of Approximate Counting via Phase Transitions

Tuesday, March 17, 2015 - 10:20am - 11:00am
Klaus 2443
Andreas Galanis (University of Oxford)
This talk will focus on the connection between phase transitions in statistical physics and the computational complexity of approximating the partition function of spin systems. A principal example of this connection is in the context of approximating the number of independent sets in graphs of bounded degree, where the uniqueness threshold on the infinite regular tree pinpoints the boundary of efficient computation.

We will be interested in establishing analogous connections when the input graph to the counting problem is further restricted to be bipartite. Specifically, we consider the complexity of counting independent sets on bipartite graphs (#BIS) and, more generally, computing the partition function of anti-ferromagnetic two-spin systems on bipartite graphs. #BIS is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #SAT to approximate. We show that #BIS on graphs of degree at most 6 is as hard to approximate as #BIS without degree bound. The degree bound 6 is the best possible as Weitz presented an FPTAS to count independent sets on graphs of maximum degree 5. Our result extends to the hard-core model and to other anti-ferromagnetic two-spin models on bipartite graphs.

Joint work with: Jin-Yi Cai, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, and Eric Vigoda.