Spin glasses are fundamental probability distributions at the core of statistical physics, the theory of average-case computational complexity, and modern high-dimensional statistical inference. In the mean-field setting, we design deterministic quasipolynomial-time algorithms for estimating the partition function to arbitrarily high accuracy for all inverse temperatures in the second moment regime. In particular, for the Sherrington--Kirkpatrick model, our algorithms succeed for the entire replica-symmetric phase. To achieve this, we study the locations of the zeros of the partition function. Notably, our methods are conceptually simple, and apply equally well to the spherical case and the case of Ising spins.

Abstract Answering a question of Gamarnik and Smedira [15], we give a polynomial time algorithm that approximately computes the volume of a truncation of a relaxation of the independent set polytope, improving on their quasi-polynomial time algorithm. Our algorithm is obtained by viewing the volume as an evaluation of a graph polynomial and we approximate this evaluation using Barvinok’s interpolation method.

Abstract We show that for any non-real algebraic number q, such that $$|q-1|>1$$ | q - 1 | > 1 or $$\Re(q)>\frac{3}{2}$$ ℜ ( q ) > 3 2 it is #P-hard to compute a multiplicative (resp. additive) approximation to the absolute value (resp. argument) of the chromatic polynomial evaluated at q on planar graphs. This implies #P-hardness for all non-real algebraic q on the family of all graphs. We, moreover, prove several hardness results for q, such that $$|q-1|\leq 1$$ | q - 1 | ≤ 1 . Our hardness results are obtained by showing that a polynomial time algorithm for approximately computing the chromatic polynomial of a planar graph at non-real algebraic q (satisfying some properties) leads to a polynomial time algorithm for exactly computing it, which is known to be hard by a result of Vertigan. Many of our results extend in fact to the more general partition function of the random cluster model, a well-known reparametrization of the Tutte polynomial.

The independence polynomial of a graph is the generating polynomial of all its independent sets. Formally, given a graph G, its independence polynomial ZG (λ) is given by ΣIλ|I|, where the sum is over all independent sets I of G. The independence polynomial has been an important object of study in both combinatorics and computer science. In particular, the algorithmic problem of estimating ZG(λ) for a fixed positive λ on an input graph G is a natural generalization of the problem of counting independent sets, and its study has led to some of the most striking connections between computational complexity and the theory of phase transitions. More surprisingly, the independence polynomial for negative and complex values of λ also turns out to be related to problems in statistical physics and combinatorics. In particular, the locations of the complex roots of the independence polynomial of bounded degree graphs turn out to be very closely related to the Lovász local lemma, and also to the questions in the computational complexity of counting. Consequently, the locations of such zeros have been studied in many works. In this direction, it is known from the work of Shearer [29] and of Scott and Sokal [27] - inspired by the study of the Lovász local lemma - that the independence polynomial ZG (λ) of a graph G of maximum degree at most d + 1 does not vanish provided that . Significant extensions of this result have recently been given in the case when λ is in the right half-plane (i.e., when ℜλ ≥ 0) by Peters and Regts [26] and Bencs and Csikvári [9]. In this paper, our motivation is to further extend these results to find new zero free regions not only in the right half plane, but also in the left half-plane, that is, when ℜλ ≤ 0. We give new geometric criterions for establishing zero-free regions as well as for carrying out semi-rigorous numerical explorations. We then provide two examples of the (rigorous) use of these criterions, by establishing two new zero-free regions in the left-half plane. We also extend the results of Bencs and Csikvári [9] for the right half-plane using our framework. By a direct application of the interpolation method of Barvinok [5], combined with extensions due to Patel and Regts [25], our results also imply deterministic polynomial time approximation algorithms for the independence polynomial of bounded degree graphs in the new zero-free regions. * The arXiv version of the paper can be accessed at https://arxiv.org/abs/2204.04868.