Motivated by a connection with the Lovasz Local Lemma, we design an algorithm to compute the multivariate independence polynomial of a graph in the "Shearer region". More generally, we can compute the independent polynomial in a natural complex extension of the Shearer region. A contribution of technical interest is a multivariate version of the correlation decay method.

The Ising model was one of the first spin systems (or graphical models) to be studied. Over the years, it has been used as a model for several phenomena rather different from its origins in statistical mechanics. Two important questions in many such applications are the related problems of sampling from the distribution given by the model, and the (approximate) computation of the so called "partition function" of the model. This talk will will look at methods for the deterministic approximation of the partition function of the Ising model, and its connections with notions of phase transitions in statistical physics. Based on joint work with Jingcheng Liu and Alistair Sinclair.

In this talk we introduce and study a partition function that counts degree-constrained subgraphs of a finite graph. In particular, our partition function generalizes the matching polynomial. Surprisingly, it is also possible to count degree-constrained orientations with the same partition function. In particular, we give a short proof to a theorem of A. Schrijver concerning a lower bound on the number of Eulerian orientations of a graph with only even degrees. We will discuss some applications to matchings too. This is joint work with Márton Borbényi.

The permanent of a Gaussian matrix is known to be #P-hard to approximate in the worst case. It is also #P-hard to compute exactly on average. Should we expect that it remains #P-hard to approximate on average? In this work we take a first step towards resolving this question: We present a quasipolynomial time deterministic algorithm for approximating the permanent of a typical n x n random matrix with unit variance and vanishing mean µ = 1/ polyloglog (n) to within inverse polynomial multiplicative error. Alternatively, one can achieve permanent approximation for matrices with mean µ=1/polylog(n) in sub-exponential time. The proposed algorithm significantly extends the regime of matrices for which efficient approximation of the permanent is known. This is because unlike previous algorithms which require a stringent correlation between the signs of the entries of the matrix it can tolerate random ensembles in which this correlation is negligible (albeit non-zero). Among important special cases we note: 1. Biased Gaussian: each entry is a complex Gaussian with unit variance 1 and mean µ. 2. Biased Bernoulli: each entry is ?1 + µ with probability 1/2, and 1 with probability 1/2. These results counter the common intuition that the difficulty of computing the permanent, even approximately, stems merely from our inability to treat matrices with many opposing signs. The Gaussian ensemble approaches the threshold of a conjectured hardness of computing the permanent of a zero-mean Gaussian matrix. This conjecture is one of the baseline assumptions of the BosonSampling paradigm that has received vast attention in recent years in the context of quantum supremacy experiments. We furthermore show that the permanent of the biased Gaussian ensemble is #P-hard to compute exactly on average. To our knowledge, this is the first natural example of a counting problem that becomes easy only when average case and approximation are combined. On a technical level, our approach stems from a recent approach taken by Barvinok who used Taylor series approximation of the logarithm of a certain univariate polynomial related to the permanent. Our main contribution is to introduce an average-case analysis of such related polynomials.

We study the problem of approximating the matching polynomial on graphs with edge parameter $\gamma$, where $\gamma$ takes arbitrary values in the complex plane. When $\gamma$ is a positive real, Jerrum and Sinclair showed that the problem has an FPRAS on general graphs. For general complex values of $\gamma$, Patel and Regts, building on methods developed by Barvinok, showed that the problem has an FPTAS on graphs of maximum degree $\Delta$ as long as $\gamma$ is not a negative real number less than or equal to $-1/(4(\Delta-1))$. Our first result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all $\Delta\geq 3$ and all real $\gamma$ less than $-1/(4(\Delta-1))$, the problem of approximating the value of the matching polynomial on graphs of maximum degree $\Delta$ with edge parameter $\gamma$ is \#P-hard. We then explore the extent to which the maximum degree parameter can be replaced by the connective constant. Sinclair et al. showed that, for positive real $\gamma$, it is possible to approximate the value of the matching polynomial using a correlation decay algorithm on graphs with bounded connective constant (and potentially unbounded maximum degree). We first show that this result does not extend in general in the complex plane; in particular, the problem is \#P-hard on graphs with bounded connective constant for a dense set of $\gamma$ values on the negative real axis. Nevertheless, we show that the result does extend for any complex value $\gamma$ that does not lie on the negative real axis. Our analysis accounts for complex values of $\gamma$ using geodesic distances in the complex plane in the metric defined by an appropriate density function. Joint work with Ivona Bezakova, Andreas Galanis, and Daniel Stefankovic.

The Ising model originated in statistical physics, where it was used to model magnetic objects. A classical result of Lee and Yang says that absence of zeros of the partition function implies no phase transition, i.e., analytic dependence on the parameters. More recently, it became clear that absence of zeros also implies the existence of efficient approximation algorithms. Another classical result of Lee and Yang confines the zeros of the partition function of the Ising model to the unit circle in the complex plane. In this talk I will give a precise description of the location of these zeros for the class of bounded degree graphs. This description is obtained using algorithmic techniques and ideas from complex dynamical systems. Based on joint work with Han Peters.

We obtain FPTAS for counting the number of independent sets and colorings for almost every random d-regular bipartite graph when the degree d is sufficient large (as a function of number of colors q in the case of counting colorings). This extends a recent result by Jenssen, Keevash and Perkins (SODA 2019) and confirms an open question raised there.

I will describe an efficient algorithm for finding the ground state of an n-particle quantum system subject to a 1D local Hamiltonian with a spectral gap. This amounts to solving for the lowest eigenvector of a succinctly described linear operator on an exponential dimensional space -- the kind of challenge that certain counting problems also encounter. This is joint work with I. Arad, U. Vazirani, and T. Vidick.

I will present a fully polynomial-time approximation scheme (FPTAS) to count the number of q-colorings for k-uniform hypergraphs with maximum degree D if k>=28 and q>315D^{14/(k?14)}, as well as an accompanying sampling algorithm with slightly worse conditions. These are the first approximate counting and sampling algorithms in the regime q<<? (for large ? and k) without any additional assumptions. In these regimes, frozen colourings are present, forming an obstacle to the standard Markov chain Monte Carlo approach. Instead, our method is based on the recent work of Moitra (STOC, 2017), in which Lovasz Local Lemma is the key ingredient. Joint work with Chao Liao, Pinyan Lu, Chihao Zhang.