We consider the problem of sampling from the ferromagnetic $q$-state Potts model on the random $d$-regular graph with parameter $β>0$. A key difficulty that arises in sampling from the model is the existence of a metastability window $(β_u,β_u')$ where the distribution has two competing modes, the so-called disordered and ordered phases, causing MCMC-based algorithms to be slow mixing from worst-case initialisations. To this end, Helmuth, Jenssen and Perkins designed a sampling algorithm that works for all $β$ when $q$ is large, using cluster expansion methods; more recently, their analysis technique has been adapted to show that random-cluster dynamics mixes fast when initialised more judiciously. However, a bottleneck behind cluster-expansion arguments is that they inherently only work for large $q$, whereas it is widely conjectured that sampling is possible for all $q,d\geq 3$. The only result so far that applies to general $q,d\geq 3$ is by Blanca and Gheissari who showed that the random-cluster dynamics mixes fast for $β<β_u$. For $β>β_u$, certain correlation phenomena emerge because of the metastability which have been hard to handle, especially for small $q$ and $d$. Our main contribution is to perform a delicate analysis of the Potts distribution and the random-cluster dynamics that goes beyond the threshold $β_u$. We use planting as the main tool in our proofs, and combine it with the analysis of random-cluster dynamics. We are thus able to show that the random-cluster dynamics initialised from all-out mixes fast for all integers $q,d\geq 3$ beyond the uniqueness threshold $β_u$; our analysis works all the way up to the threshold $β_c\in (β_u,β_u')$ where the dominant mode switches from disordered to ordered. We also obtain an algorithm in the ordered regime $β>β_c$ that refines significantly the range of $q,d$.

Consider a $k$-SAT formula $Φ$ where every variable appears at most $d$ times. Let $σ$ be a satisfying assignment, sampled proportionally to $e^{βm(σ)}$ where $m(σ)$ is the number of true variables and $β$ is a real parameter. Given $Φ$ and $σ$, can we efficiently learn $β$? This problem falls into a recent line of work about single-sample (``one-shot'') learning of Markov random fields. Our $k$-SAT setting was recently studied by Galanis, Kalavasis, Kandiros (SODA24). They showed that single-sample learning is possible when roughly $d\leq 2^{k/6.45}$ and impossible when $d\geq (k+1) 2^{k-1}$. In addition to the gap in~$d$, their impossibility result left open the question of whether the feasibility threshold for one-shot learning is dictated by the satisfiability threshold for bounded-degree $k$-SAT formulas. Our main contribution is to answer this question negatively. We show that one-shot learning for $k$-SAT is infeasible well below the satisfiability threshold; in fact, we obtain impossibility results for degrees $d$ as low as $k^2$ when $β$ is sufficiently large, and bootstrap this to small values of $β$ when $d$ scales exponentially with $k$, via a probabilistic construction. On the positive side, we simplify the analysis of the learning algorithm, obtaining significantly stronger bounds on $d$ in terms of $β$. For the uniform case $β\rightarrow 0$, we show that learning is possible under the condition $d\lesssim 2^{k/2}$. This is (up to constant factors) all the way to the sampling threshold -- it is known that sampling a uniformly-distributed satisfying assignment is NP-hard for $d\gtrsim 2^{k/2}$.

Consider a k -SAT formula Φ where every variable appears at most d times, and let σ be a satisfying assignment of Φ sampled proportionally to e β m ( σ ) where m ( σ ) is the number of variables set to true and β is a real parameter. Given Φ and σ , can we learn the value of β efficiently? This problem falls into a recent line of works about single-sample (“one-shot”) learning of Markov random fields. The k -SAT setting we consider here was recently studied by Galanis, A., Kalavasis, A., Kandiros, A.V., 2024. Learning hard-constrained models with one sample. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 3184–3196. They showed that single-sample learning is possible when roughly d ≤ 2 k / 6.45 and impossible when d ≥ ( k + 1 ) 2 k − 1 . Crucially, for their impossibility results they used the existence of unsatisfiable instances which, aside from the gap in d , left open the question of whether the feasibility threshold for one-shot learning is dictated by the satisfiability threshold of k -SAT formulas of bounded degree. Our main contribution is to answer this question negatively. We show that one-shot learning for k -SAT is infeasible well below the satisfiability threshold; in fact, we obtain impossibility results for degrees d as low as k 2 when β is sufficiently large, and bootstrap this to small values of β when d scales exponentially with k , via a probabilistic construction. On the positive side, we simplify the analysis of the learning algorithm and obtain significantly stronger bounds on d in terms of β . In particular, for the uniform case β → 0 that has been studied extensively in the sampling literature, our analysis shows that learning is possible under the condition d ≲ 2 k / 2 . Note that this is (up to constant factors) all the way to the sampling threshold – it is known that sampling a uniformly-distributed satisfying assignment is NP-hard for d ≳ 2 k / 2 .

We consider the problem of sampling from the Ising model when the underlying interaction matrix has eigenvalues lying within an interval of length $γ$. Recent work in this setting has shown various algorithmic results that apply roughly when $γ< 1$, notably with nearly-linear running times based on the classical Glauber dynamics. However, the optimality of the range of $γ$ was not clear since previous inapproximability results developed for the antiferromagnetic case (where the matrix has entries $\leq 0$) apply only for $γ>2$. To this end, Kunisky (SODA'24) recently provided evidence that the problem becomes hard already when $γ>1$ based on the low-degree hardness for an inference problem on random matrices. Based on this, he conjectured that sampling from the Ising model in the same range of $γ$ is NP-hard. Here we confirm this conjecture, complementing in particular the known algorithmic results by showing NP-hardness results for approximately counting and sampling when $γ>1$, with strong inapproximability guarantees; we also obtain a more refined hardness result for matrices where only a constant number of entries per row are allowed to be non-zero. The main observation in our reductions is that, for $γ>1$, Glauber dynamics mixes slowly when the interactions are all positive (ferromagnetic) for the complete and random regular graphs, due to a bimodality in the underlying distribution. While ferromagnetic interactions typically preclude NP-hardness results, here we work around this by introducing in an appropriate way mild antiferromagnetism, keeping the spectrum roughly within the same range. This allows us to exploit the bimodality of the aforementioned graphs and show the target NP-hardness by adapting suitably previous inapproximability techniques developed for antiferromagnetic systems.

We consider the problem of estimating the parameters of a Markov Random Field with hard-constraints using a single sample. As our main running examples, we use the k-SAT and the proper coloring models, as well as general H-coloring models; for all of these we obtain both positive and negative results. In contrast to the soft-constrained case, we show in particular that single-sample estimation is not always possible, and that the existence of an estimator is related to the existence of non-satisfiable instances.

Abstract. We give a nearly linear-time algorithm to approximately sample satisfying assignments in the random [Formula: see text]-SAT model when the density of the formula scales exponentially with [Formula: see text]. The best previously known sampling algorithm for the random [Formula: see text]-SAT model applies when the density [Formula: see text] of the formula is less than [Formula: see text] and runs in time [Formula: see text] [Galanis et al., SIAM J. Comput., 50 (2021), pp. 1701–1738]. Here [Formula: see text] is the number of variables and [Formula: see text] is the number of clauses. Our algorithm achieves a significantly faster running time of [Formula: see text] and samples satisfying assignments up to density [Formula: see text]. The main challenge in our setting is the presence of many variables with unbounded degree, which causes significant correlations within the formula and impedes the application of relevant Markov chain methods from the bounded-degree setting [Feng et al., J. ACM, 68 (2021) 40; Jain, Pham, and Vuong, On the Sampling Lovász Local Lemma for Atomic Constraint Satisfaction Problems, 2021]. Our main technical contribution is a [Formula: see text] bound of the sum of influences in the [Formula: see text]-SAT model which turns out to be robust against the presence of high-degree variables. This allows us to apply the spectral independence framework and obtain fast mixing results of a uniform-block Glauber dynamics on a carefully selected subset of the variables. The final key ingredient in our method is to take advantage of the sparsity of logarithmic-sized connected sets and the expansion properties of the random formula, and establish relevant connectivity properties of the set of satisfying assignments that enable the fast simulation of this Glauber dynamics. Our results also allow us to conclude that, with high probability, a random [Formula: see text]-CNF formula with density at most [Formula: see text] has a giant component of solutions that are connected in a graph where solutions are adjacent if they have Hamming distance [Formula: see text]. We are also able to deduce looseness results for random [Formula: see text]-CNFs in the same regime.

Spectral independence is a recently developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L p -norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, and Yin, FOCS’13). The non-linearity of L p -norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L p -analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G (n, d/n) , where the previously known algorithms run in time n O (log d ) or applied only to large d . We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d , throughout the uniqueness regime.

We consider the performance of Glauber dynamics for the random cluster model with real parameter $q>1$ and temperature $β>0$. Recent work by Helmuth, Jenssen and Perkins detailed the ordered/disordered transition of the model on random $Δ$-regular graphs for all sufficiently large $q$ and obtained an efficient sampling algorithm for all temperatures $β$ using cluster expansion methods. Despite this major progress, the performance of natural Markov chains, including Glauber dynamics, is not yet well understood on the random regular graph, partly because of the non-local nature of the model (especially at low temperatures) and partly because of severe bottleneck phenomena that emerge in a window around the ordered/disordered transition. Nevertheless, it is widely conjectured that the bottleneck phenomena that impede mixing from worst-case starting configurations can be avoided by initialising the chain more judiciously. Our main result establishes this conjecture for all sufficiently large $q$ (with respect to $Δ$). Specifically, we consider the mixing time of Glauber dynamics initialised from the two extreme configurations, the all-in and all-out, and obtain a pair of fast mixing bounds which cover all temperatures $β$, including in particular the bottleneck window. Our result is inspired by the recent approach of Gheissari and Sinclair for the Ising model who obtained a similar-flavoured mixing-time bound on the random regular graph for sufficiently low temperatures. To cover all temperatures in the RC model, we refine appropriately the structural results of Helmuth, Jenssen and Perkins about the ordered/disordered transition and show spatial mixing properties "within the phase", which are then related to the evolution of the chain.

The independent set polynomial is important in many areas of combinatorics, computer science, and statistical physics. For every integer Δ≥2, the Shearer threshold is the value λ⁎(Δ)=(Δ−1)Δ−1/ΔΔ. It is known that for λ<−λ⁎(Δ), there are graphs G with maximum degree Δ whose independent set polynomial, evaluated at λ, is at most 0. Also, there are no such graphs for any λ>−λ⁎(Δ). This paper is motivated by the computational problem of approximating the independent set polynomial when λ<−λ⁎(Δ). The key issue in complexity bounds for this problem is “implementation”. Informally, an implementation of a real number λ′ is a graph whose hard-core partition function, evaluated at λ, simulates a vertex-weight of λ′ in the sense that λ′ is the ratio between the contribution to the partition function from independent sets containing a certain vertex and the contribution from independent sets that do not contain that vertex. Implementations are the cornerstone of intractability results for the problem of approximately evaluating the independent set polynomial. Our main result is that, for any λ<−λ⁎(Δ), it is possible to implement a set of values that is dense over the reals. The result is tight in the sense that it is not possible to implement a set of values that is dense over the reals for any λ>λ⁎(Δ). Our result has already been used in a paper with Bezáková (STOC 2018) to show that it is #P-hard to approximate the evaluation of the independent set polynomial on graphs of degree at most Δ at any value λ<−λ⁎(Δ). In the appendix, we give an additional incomparable inapproximability result (strengthening the inapproximability bound to an exponential factor, but weakening the hardness to NP-hardness).

Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal $O(n \log n)$ sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using $L^p$-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS'13). The non-linearity of $L^p$-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the $L^p$-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph $G(n,d/n)$, where the previously known algorithms run in time $n^{O(\log d)}$ or applied only to large $d$. We refine these algorithmic bounds significantly, and develop fast $n^{1+o(1)}$ algorithms based on Glauber dynamics that apply to all $d$, throughout the uniqueness regime.

We study the performance of Markov chains for the $q$-state ferromagnetic Potts model on random regular graphs. It is conjectured that their performance is dictated by metastability phenomena, i.e., the presence of "phases" (clusters) in the sample space where Markov chains with local update rules, such as the Glauber dynamics, are bound to take exponential time to escape. The phases that are believed to drive these metastability phenomena in the case of the Potts model emerge as local, rather than global, maxima of the so-called Bethe functional, and previous approaches of analysing these phases based on optimisation arguments fall short of the task. Our first contribution is to detail the emergence of the metastable phases for the $q$-state Potts model on the $d$-regular random graph for all integers $q,d\geq 3$, and establish that for an interval of temperatures, which is delineated by the uniqueness and a broadcasting threshold on the $d$-regular tree, the two phases coexist. The proofs are based on a conceptual connection between spatial properties and the structure of the Potts distribution on the random regular graph, rather than complicated moment calculations. Based on this new structural understanding of the model, we obtain various algorithmic consequences. We first complement recent fast mixing results for Glauber dynamics by Blanca and Gheissari below the uniqueness threshold, showing an exponential lower bound on the mixing time above the uniqueness threshold. Then, we obtain tight results even for the non-local Swendsen-Wang chain, where we establish slow mixing/metastability for the whole interval of temperatures where the chain is conjectured to mix slowly on the random regular graph. The key is to bound the conductance of the chains using a random graph "planting" argument combined with delicate bounds on random-graph percolation.

We give an FPRAS for counting q-colorings for even on almost every Δ-regular bipartite graph. This improves significantly upon the previous best bound of by Jenssen, Keevash, and Perkins (SODA'19). Analogously, for the hard-core model on independentsets weighted by λ > 0, we present an FPRAS for estimating the partition function when , which improves upon previous results by an Ω(log Δ) factor. Our results for the colorings and hard-core models follow from a general result that applies to arbitrary spin systems. Our main contribution is to show how to elevate probabilistic/analytic bounds on the marginal probabilities for the typical structure of phases on random bipartite regular graphs into efficient algorithms, using the polymer method. We further show evidence that our results for colorings and independent sets are within a constant factor of best possible using current polymer-method approaches.

Abstract We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q $$\geq$$ ≥ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.

The polymer model framework is a classical tool from statistical mechanics that has recently been used to obtain approximation algorithms for spin systems on classes of bounded-degree graphs; examples include the ferromagnetic Potts model on expanders and on the grid. One of the key ingredients in the analysis of polymer models is controlling the growth rate of the number of polymers, which has been typically achieved so far by invoking the bounded-degree assumption. Nevertheless, this assumption is often restrictive and obstructs the applicability of the method to more general graphs. For example, sparse random graphs typically have bounded average degree and good expansion properties, but they include vertices with unbounded degree, and therefore are excluded from the current polymer-model framework. We develop a less restrictive framework for polymer models that relaxes the standard bounded-degree assumption, by reworking the relevant polymer models from the edge perspective. The edge perspective allows us to bound the growth rate of the number of polymers in terms of the total degree of polymers, which in turn can be related more easily to the expansion properties of the underlying graph. To apply our methods, we consider random graphs with unbounded degrees from a fixed degree sequence (with minimum degree at least 3) and obtain approximation algorithms for the ferromagnetic Potts model, which is a standard benchmark for polymer models. Our techniques also extend to more general spin systems.

We study the complexity of approximating the partition function $Z_{\mathrm{Ising}}(G; \beta)$ of the Ising model in terms of the relation between the edge interaction $\beta$ and a parameter $\Delta$ which is an upper bound on the maximum degree of the input graph $G$. Following recent trends in both statistical physics and algorithmic research, we allow the edge interaction $\beta$ to be any complex number. Many recent partition function results focus on complex parameters, both because of physical relevance and because of the key role of the complex case in delineating the tractability/intractability phase transition of the approximation problem. In this work we establish both new tractability results and new intractability results. Our tractability results show that $Z_{\mathrm{Ising}}(-; \beta)$ has an FPTAS when $\lvert \beta - 1 \rvert / \lvert \beta + 1 \rvert < \tan(\pi / (4 \Delta - 4))$. The core of the proof is showing that there are no inputs $G$ that make the partition function $0$ when $\beta$ is in this range. Our result significantly extends the known zero-free region of the Ising model (and hence the known approximation results). Our intractability results show that it is $\mathrm{\#P}$-hard to multiplicatively approximate the norm and to additively approximate the argument of $Z_{\mathrm{Ising}}(-; \beta)$ when $\beta \in \mathbb{C}$ is an algebraic number such that $\beta \not \in \mathbb{R} \cup \{i, -i\}$ and $\lvert \beta - 1\rvert / \lvert \beta + 1 \rvert > 1 / \sqrt{\Delta - 1}$. These are the first results to show intractability of approximating $Z_{\mathrm{Ising}}(-, \beta)$ on bounded degree graphs with complex $\beta$. Moreover, we demonstrate situations in which zeros of the partition function imply hardness of approximation in the Ising model.

We study the computational complexity of approximating the partition function of the ferromagnetic Ising model in the Lee-Yang circle of zeros given by |λ| = 1, where λ is the external field of the model. Complex-valued parameters for the Ising model are relevant for quantum circuit computations and phase transitions in statistical physics, but have also been key in the recent deterministic approximation scheme for all |λ| ≠ 1 by Liu, Sinclair, and Srivastava. Here, we focus on the unresolved complexity picture on the unit circle, and on the tantalising question of what happens in the circular arc around λ = 1, where on one hand the classical algorithm of Jerrum and Sinclair gives a randomised approximation scheme on the real axis suggesting tractability, and on the other hand the presence of Lee-Yang zeros alludes to computational hardness. Our main result establishes a sharp computational transition at the point λ = 1; in fact, our techniques apply more generally to the whole unit circle |λ| = 1. We show #P-hardness for approximating the partition function on graphs of maximum degree Δ when b, the edge-interaction parameter, is in the interval and λ is a non-real on the unit circle. This result contrasts with known approximation algorithms when , and shows that the Lee-Yang circle of zeros is computationally intractable, even on bounded-degree graphs. Our inapproximability result is based on constructing rooted tree gadgets via a detailed understanding of the underlying dynamical systems, which are further parameterised by the degree of the root. The ferromagnetic Ising model has radically different behaviour than previously considered anti-ferromagnetic models, and showing our #P-hardness results in the whole Lee-Yang circle requires a new high-level strategy to construct the gadgets. To this end, we devise an elaborate inductive procedure to construct the required gadgets by taking into account the dependence between the degree of the root of the tree and the magnitude of the derivative at the fixpoint of the corresponding dynamical system. The full version (with all proofs) is available on arXiv at arxiv.org/abs/2006.14828.

The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber dynamics for the hard-core model defined on weighted independent sets. We develop the spectral independence approach for colorings, and obtain new algorithmic results for the corresponding counting/sampling problems. Let α∗ ≈ 1.763 denote the solution to exp(1/x) = x and let α > α∗. We prove that, for any triangle-free graph G = (V, E) with maximum degree Δ, for all q ≥ αΔ + 1, the mixing time of the Glauber dynamics for q-colorings is polynomial in n = |V|, with the exponent of the polynomial independent of Δ and q. In comparison, previous approximate counting results for colorings held for a similar range of q (asymptotically in Δ) but with larger girth requirement or with a running time where the polynomial exponent depended on Δ and q (exponentially). One further feature of using the spectral independence approach to study colorings is that it avoids many of the technical complications in previous approaches caused by coupling arguments or by passing to the complex plane; the key improvement on the running time is based on relatively simple combinatorial arguments which are then translated into spectral bounds.

We give the first efficient algorithm to approximately count the number of solutions in the random $k$-SAT model when the density of the formula scales exponentially with $k$. The best previous counting algorithm for the permissive version of the model was due to Montanari and Shah and was based on the correlation decay method, which works up to densities $(1+o_k(1))\frac{2\log k}{k}$, the Gibbs uniqueness threshold for the model. Instead, our algorithm harnesses a recent technique by Moitra to work for random formulas with much higher densities. The main challenge in our setting is to account for the presence of high-degree variables whose marginal distributions are hard to control and which cause significant correlations within the formula.

We prove that, unless P=NP, there is no polynomial-time algorithm to approximate within some multiplicative constant the average size of an independent set in graphs of maximum degree 6. This is a special case of a more general result for the hard-core model defined on independent sets weighted by a parameter . In the general setting, we prove that, unless P=NP, for all Δ ≥ 3, all , there is no FPTAS which applies to all graphs of maximum degree Δ for computing the average size of the independent set in the Gibbs distribution, where λc(Δ) is the critical point for the uniqueness/non-uniqueness phase transition on the Δ-regular tree. Moreover, we prove that for λ in a dense set of this non-uniqueness region the problem is NP-hard to approximate within some constant factor. Our work extends to the antiferromagnetic Ising model and generalizes to all 2-spin antiferromagnetic models, establishing hardness of computing the average magnetization in the tree non-uniqueness region. Previously, Schulman, Sinclair and Srivastava (2015) showed that it is #P-hard to compute the average magnetization exactly, but no hardness of approximation results were known. Hardness results of Sly (2010) and Sly and Sun (2014) for approximating the partition function do not imply hardness of computing averages. The new ingredient in our reduction is an intricate construction of pairs of rooted trees whose marginal distributions at the root agree but their derivatives disagree. The main technical contribution is controlling what marginal distributions and derivatives are achievable and using Cauchy's functional equation to argue existence of the gadgets. The full version of this paper with detailed proofs to all lemmas and theorems can be found out at https://arxiv.org/abs/2004.09238.

We give the first efficient algorithm to approximately count the number of solutions in the random $k$-SAT model when the density of the formula scales exponentially with $k$. The best previous counting algorithm for the permissive version of the model was due to Montanari and Shah and was based on the correlation decay method, which works up to densities $(1+o_k(1))\frac{2\log k}{k}$, the Gibbs uniqueness threshold for the model. Instead, our algorithm harnesses a recent technique by Moitra to work for random formulas. The main challenge in our setting is to account for the presence of high-degree variables whose marginal distributions are hard to control and which cause significant correlations within the formula.

We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q ≥ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.

We study the complexity of approximating the value of the independent set polynomial $Z_G(\lambda)$ of a graph $G$ with maximum degree $\Delta$ when the activity $\lambda$ is a complex number. When $\lambda$ is real, the complexity picture is well understood, and is captured by two real-valued thresholds $\lambda^*$ and $\lambda_c$, which depend on $\Delta$ and satisfy $0<\lambda^*<\lambda_c$. It is known that if $\lambda$ is a real number in the interval $(-\lambda^*,\lambda_c)$ then there is a fully polynomial time approximation scheme (FPTAS) for approximating $Z_G(\lambda)$ on graphs $G$ with maximum degree at most $\Delta$. On the other hand, if $\lambda$ is a real number outside of the (closed) interval, then approximation is NP-hard. The key to establishing this picture was the interpretation of the thresholds $\lambda^*$ and $\lambda_c$ on the $\Delta$-regular tree. The “occupation ratio” of a $\Delta$-regular tree $T$ is the contribution to $Z_T(\lambda)$ from independent sets containing the root of the tree, divided by $Z_T(\lambda)$ itself. This occupation ratio converges to a limit, as the height of the tree grows, if and only if $\lambda\in [-\lambda^*,\lambda_c]$. Unsurprisingly, the case where $\lambda$ is complex is more challenging. It is known that there is an FPTAS when $\lambda$ is a complex number with norm at most $\lambda^*$ and also when $\lambda$ is in a small strip surrounding the real interval $[0,\lambda_c)$. However, neither of these results is believed to fully capture the truth about when approximation is possible. Peters and Regts identified the complex values of $\lambda$ for which the occupation ratio of the $\Delta$-regular tree converges. These values carve a cardioid-shaped region $\Lambda_\Delta$ in the complex plane, whose boundary includes the critical points $-\lambda^*$ and $\lambda_c$. Motivated by the picture in the real case, they asked whether $\Lambda_\Delta$ marks the true approximability threshold for general complex values $\lambda$. Our main result shows that for every $\lambda$ outside of $\Lambda_\Delta$, the problem of approximating $Z_G(\lambda)$ on graphs $G$ with maximum degree at most $\Delta$ is indeed NP-hard. In fact, when $\lambda$ is outside of $\Lambda_\Delta$ and is not a positive real number, we give the stronger result that approximating $Z_G(\lambda)$ is actually \#P-hard. Further, on the negative real axis, when $\lambda < - \lambda^*$, we show that it is \#P-hard to even decide whether $Z_G(\lambda)>0$, resolving in the affirmative a conjecture of Harvey, Srivastava, and Vondrák. Our proof techniques are based around tools from complex analysis---specifically the study of iterative multivariate rational maps.

We consider the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the so-called uniqueness regime of the regular tree, but positive algorithmic results have been for the most part elusive. In this paper, for all integers $q\geq 3$ and $\Delta\geq 3$, we develop algorithms that produce samples within error $o(1)$ from the $q$-state Potts model on random $\Delta$-regular graphs, whenever the temperature is in uniqueness, for both the ferromagnetic and antiferromagnetic cases. The algorithm for the antiferromagnetic Potts model is based on iteratively adding the edges of the graph and resampling a bichromatic class that contains the endpoints of the newly added edge. Key to the algorithm is how to perform the resampling step efficiently since bichromatic classes can potentially induce linear-sized components. To this end, we exploit the tree uniqueness to show that the average growth of bichromatic components is typically small, which allows us to use correlation decay algorithms for the resampling step. While the precise uniqueness threshold on the tree is not known for general values of $q$ and $\Delta$ in the antiferromagnetic case, our algorithm works throughout uniqueness regardless of its value. In the case of the ferromagnetic Potts model, we are able to simplify the algorithm significantly by utilizing the random-cluster representation of the model. In particular, we demonstrate that a percolation-type algorithm succeeds in sampling from the random-cluster model with parameters $p,q$ on random $\Delta$-regular graphs for all values of $q\geq 1$ and $p

We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {u,v} with distance d> 1 is added as a “long-range” edge with probability proportional to d -r , where r≥ 0 is a parameter of the model. Kleinberg [33{ studied a close variant of this network model and proved that the (decentralised) routing time is O((log n ) 2 ) when r =2 and n Ω (1) when r≠ 2. Here, we prove that the random walk also undergoes a phase transition at r=2 , but in this case, the phase transition is of a different form. We establish that the mixing time is ϴ (log n) for r< 2, O((log n ) 4 ) for r =2, and n Ω (1) for r> 2.

For spin systems, such as the hard-core model on independent sets weighted by fugacity lambda>0, efficient algorithms for the associated approximate counting/sampling problems typically apply in the high-temperature region, corresponding to low fugacity. Recent work of Jenssen, Keevash and Perkins (2019) yields an FPTAS for approximating the partition function (and an efficient sampling algorithm) on bounded-degree (bipartite) expander graphs for the hard-core model at sufficiently high fugacity, and also the ferromagnetic Potts model at sufficiently low temperatures. Their method is based on using the cluster expansion to obtain a complex zero-free region for the partition function of a polymer model, and then approximating this partition function using the polynomial interpolation method of Barvinok. We present a simple discrete-time Markov chain for abstract polymer models, and present an elementary proof of rapid mixing of this new chain under sufficient decay of the polymer weights. Applying these general polymer results to the hard-core and ferromagnetic Potts models on bounded-degree (bipartite) expander graphs yields fast algorithms with running time O(n log n) for the Potts model and O(n^2 log n) for the hard-core model, in contrast to typical running times of n^{O(log Delta)} for algorithms based on Barvinok’s polynomial interpolation method on graphs of maximum degree Delta. In addition, our approach via our polymer model Markov chain is conceptually simpler as it circumvents the zero-free analysis and the generalization to complex parameters. Finally, we combine our results for the hard-core and ferromagnetic Potts models with standard Markov chain comparison tools to obtain polynomial mixing time for the usual spin system Glauber dynamics restricted to even and odd or "red" dominant portions of the respective state spaces.

Strong spatial mixing (SSM) is a form of correlation decay that has played an essential role in the design of approximate counting algorithms for spin systems. A notable example is the algorithm of Weitz (2006) for the hard-core model on weighted independent sets. We study SSM for the q-colorings problem on the infinite (d+1)-regular tree. Weak spatial mixing (WSM) captures whether the influence of the leaves on the root vanishes as the height of the tree grows. Jonasson (2002) established WSM when q>d+1. In contrast, in SSM, we first fix a coloring on a subset of internal vertices, and we again ask if the influence of the leaves on the root is vanishing. It was known that SSM holds on the (d+1)-regular tree when q>alpha d where alpha ~~ 1.763... is a constant that has arisen in a variety of results concerning random colorings. Here we improve on this bound by showing SSM for q>1.59d. Our proof establishes an L^2 contraction for the BP operator. For the contraction we bound the norm of the BP Jacobian by exploiting combinatorial properties of the coloring of the tree.

Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of the partition function of antiferromagnetic 2-spin models. Previous analyses of correlation-decay algorithms implicitly depended on the occurrence of strong spatial mixing. This, roughly, means that one uses worst-case analysis of the recursive procedure that creates the subinstances. In this paper, we develop a new analysis method that is more refined than the worst-case analysis. We take the shape of instances in the computation tree into consideration and we amortize against certain “bad” instances that are created as the recursion proceeds. This enables us to show correlation decay and to obtain a fully polynomial-time approximation scheme (FPTAS) even when strong spatial mixing fails. We apply our technique to the problem of approximately counting independent sets in hypergraphs with degree upper bound $\Delta$ and with a lower bound $k$ on the arity of hyperedges. Liu and Lin gave an FPTAS for $k\geq2$ and $\Delta\leq5$ (lack of strong spatial mixing was the obstacle preventing this algorithm from being generalized to $\Delta=6$). Our technique gives a tight result for $\Delta=6$, showing that there is an FPTAS for $k\geq3$ and $\Delta\leq6$. The best previously known approximation scheme for $\Delta=6$ is the Markov-chain simulation based fully polynomial-time randomized approximation scheme (FPRAS) of Bordewich, Dyer, and Karpinski, which only works for $k\geq8$. Our technique also applies for larger values of $k$, giving an FPTAS for $k\geq\Delta$. This bound is not substantially stronger than existing randomized results in the literature. Nevertheless, it gives the first deterministic approximation scheme in this regime. Moreover, unlike existing results, it leads to an FPTAS for counting dominating sets in regular graphs with sufficiently large degree. We further demonstrate that in the hypergraph independent set model, approximating the partition function is NP-hard even within the uniqueness regime. Also, approximately counting dominating sets of bounded-degree graphs (without the regularity restriction) is NP-hard.

We consider the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the uniqueness regime of the regular tree, but positive algorithmic results have been for the most part elusive. In this paper, for all integers $q\geq 3$ and $Δ\geq 3$, we develop algorithms that produce samples within error $o(1)$ from the $q$-state Potts model on random $Δ$-regular graphs, whenever the temperature is in uniqueness, for both the ferromagnetic and antiferromagnetic cases. The algorithm for the antiferromagnetic Potts model is based on iteratively adding the edges of the graph and resampling a bichromatic class that contains the endpoints of the newly added edge. Key to the algorithm is how to perform the resampling step efficiently since bichromatic classes may induce linear-sized components. To this end, we exploit the tree uniqueness to show that the average growth of bichromatic components is typically small, which allows us to use correlation decay algorithms for the resampling step. While the precise uniqueness threshold on the tree is not known for general values of $q$ and $Δ$ in the antiferromagnetic case, our algorithm works throughout uniqueness regardless of its value. In the case of the ferromagnetic Potts model, we simplify the algorithm significantly by utilising the random-cluster representation of the model. In particular, we show that a percolation-type algorithm succeeds in sampling from the random-cluster model with parameters $p,q$ on random $Δ$-regular graphs for all values of $q\geq 1$ and $p

The Gibbs sampler is the most popular Markov chain used for learning and inference problems in Graphical Models (GM). These tasks are computationally intractable in general, and the Gibbs sampler often suffers from slow mixing. In this paper, we study the Swendsen-Wang dynamics which is a more sophisticated Markov chain designed to overcome bottlenecks that impede Gibbs sampler. We prove O(log n) mixing time for attractive binary pairwise GMs (i.e., ferromagnetic Ising models) on stochastic partitioned graphs having n vertices, under some mild conditions including low temperature regions where the Gibbs sampler provably mixes exponentially slow. Our experiments also confirm that the Swendsen-Wang sampler significantly outperforms the Gibbs sampler for learning parameters of attractive GMs.

We study the problem of approximately evaluating the independent set polynomial of bounded-degree graphs at a point lambda or, equivalently, the problem of approximating the partition function of the hard-core model with activity lambda on graphs G of max degree D. For lambda>0, breakthrough results of Weitz and Sly established a computational transition from easy to hard at lambda_c(D)=(D-1)^(D-1)/(D-2)^D, which coincides with the tree uniqueness phase transition from statistical physics. For lambda<0, the evaluation of the independent set polynomial is connected to the conditions of the Lovasz Local Lemma. Shearer identified the threshold lambda*(D)=(D-1)^(D-1)/D^D as the maximum value p such that every family of events with failure probability at most p and whose dependency graph has max degree D has nonempty intersection. Very recently, Patel and Regts, and Harvey et al. have independently designed FPTASes for approximating the partition function whenever |lambda| =3, for all lambda<-lambda*(D), it is NP-hard to approximate the partition function on graphs of maximum degree D, even within an exponential factor. Thus, our result, combined with the FPTASes for lambda>-lambda*(D), establishes a phase transition for negative activities. In fact, we now have the following picture for the problem of approximating the partition function with activity lambda on graphs G of max degree D. 1. For -lambda*(D) lambda_c(D), the problem is NP-hard. Rather than the tree uniqueness threshold of the positive case, the phase transition for negative activities corresponds to the existence of zeros for the partition function of the tree below -lambda*(D).

We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language Gamma and a degree bound Delta, we study the complexity of #CSP_Delta(Gamma), which is the problem of counting satisfying assignments to CSP instances with constraints from Gamma and whose variables can appear at most Delta times. Our main result shows that: (i) if every function in Gamma is affine, then #CSP_Delta(Gamma) is in FP for all Delta, (ii) otherwise, if every function in Gamma is in a class called IM_2, then for all sufficiently large Delta, #CSP_Delta(Gamma) is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large Delta, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSP_Delta(Gamma), even within an exponential factor. Our result extends previous results, which apply only in the so-called "conservative" case.

The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness r > 1. All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or nonmutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected, then the algorithm will eventually reach fixation , in which all individuals are mutants, or extinction , in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every r > 1, the extinction probability tends to 0 as the number of vertices increases. A formal definition is provided in the article. Strong amplification is a rather surprising property—it means that in such graphs, the fixation probability of a uniformly placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of r > 1 (independently of n ). The name “strongly amplifying” comes from the fact that this selective advantage is “amplified.” Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly amplifying families—superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this article, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family “megastars.” When the algorithm is run on an n -vertex graph in this family, starting with a uniformly chosen mutant, the extinction probability is roughly n − 1/2 (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of n ). Finally, we prove that our analysis of megastars is fairly tight—there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al.

We examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph or a reflexive proper interval graph then approximately counting list H-colourings is equivalent to #BIS, the problem of approximately counting independent sets in a bipartite graph. This is a well-studied problem which is believed to be of intermediate complexity - it is believed that it does not have an FPRAS, but that it is not as difficult as approximating the most difficult counting problems in #P. For every other graph H, approximately counting list H-colourings is complete for #P with respect to approximation-preserving reductions (so there is no FPRAS unless NP = RP). Two pleasing features of the trichotomy are (i) it has a natural formulation in terms of hereditary graph classes, and (ii) the proof is largely self-contained and does not require any universal algebra (unlike similar dichotomies in the weighted case). We are able to extend the hardness results to the bounded-degree setting, showing that all hardness results apply to input graphs with maximum degree at most 6.

One of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferromagnetic 2-spin systems on bounded-degree graphs. This classification is based on a beautiful connection to the so-called uniqueness phase transition from statistical physics on the infinite Δ-regular tree. Our objective is to study the impact of this classification on unweighted 2-spin models on k-uniform hypergraphs. As has already been indicated by Yin and Zhao, the connection between the uniqueness phase transition and the complexity of approximate counting breaks down in the hypergraph setting. Nevertheless, we show that for every non-trivial symmetric k-ary Boolean function f there exists a degree bound Δ0 so that for all Δ ≥ Δ0 the following problem is NP-hard: given a k-uniform hypergraph with maximum degree at most Δ, approximate the partition function of the hypergraph 2-spin model associated with f. It is NP-hard to approximate this partition function even within an exponential factor. By contrast, if f is a trivial symmetric Boolean function (e.g., any function f that is excluded from our result), then the partition function of the corresponding hypergraph 2-spin model can be computed exactly in polynomial time. The full version of this paper is available at arxiv.org/abs/1505.06146. For the convenience of the reader, we have also included in the theorem statements the number of the respective theorem in the full version.

We consider the problem of counting $H$-colorings from an input graph $G$ to a target graph $H$. We show that if $H$ is any fixed graph without trivial components, then the problem is as hard as the well-known problem $\#\mathrm{BIS}$, which is the problem of (approximately) counting independent sets in a bipartite graph. $\#\mathrm{BIS}$ is a complete problem in an important complexity class for approximate counting, and is believed not to have a fully polynomial randomized approximation scheme (FPRAS). If this is so, then our result shows that for every graph $H$ without trivial components, the $H$-coloring counting problem has no FPRAS. This problem was studied a decade ago by Goldberg, Kelk, and Paterson. They were able to show that approximately sampling $H$-colorings is $\#\mathrm{BIS}$-hard, but it was not known how to get the result for approximate counting. Our solution builds on nonconstructive ideas using the work of Lovász.

Recent results establish for the hard-core model (and more generally for 2-spin antiferromagnetic systems) that the computational complexity of approximating the partition function on graphs of maximum degree $\Delta$ undergoes a phase transition that coincides with the uniqueness/non-uniqueness phase transition on the infinite $\Delta$-regular tree. For the ferromagnetic Potts model we investigate whether analogous hardness results hold. Goldberg and Jerrum showed that approximating the partition function of the ferromagnetic Potts model is at least as hard as approximating the number of independent sets in bipartite graphs, so-called #BIS-hardness. We improve this hardness result by establishing it for bipartite graphs of maximum degree $\Delta$. To this end, we first present a detailed picture for the phase diagram for the infinite $\Delta$-regular tree, giving a refined picture of its first-order phase transition and establishing the critical temperature for the coexistence of the disordered and ordered phases. We then prove for all temperatures below this critical temperature (corresponding to the region where the ordered phase “dominates'') that it is #BIS-hard to approximate the partition function on bipartite graphs of maximum degree $\Delta$. As a simple corollary of this result, we obtain that it is #BIS-hard to approximate the number of $k$-colorings on bipartite graphs of maximum degree $\Delta$ whenever $k\leq \Delta/(2\ln \Delta)$. The #BIS-hardness result for the ferromagnetic Potts model uses random bipartite regular graphs as a gadget in the reduction. The analysis of these random graphs relies on recent results establishing connections between the maxima of the expectation of their partition function, attractive fixpoints of the associated tree recursions, and induced matrix norms. In this paper we extend these connections to random regular graphs for all ferromagnetic models. Using these connections, we establish the Bethe prediction for every ferromagnetic spin system on random regular graphs, which says roughly that the expectation of the log of the partition function $Z$ is the same as the log of the expectation of $Z$. As a further consequence of our results, we prove for the ferromagnetic Potts model that the Swendsen--Wang algorithm is torpidly mixing (i.e., exponentially slow convergence to its stationary distribution) on random $\Delta$-regular graphs at the critical temperature for sufficiently large $q$.

A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree Δ undergoes a phase transition that coincides with the statistical physics uniqueness/nonuniqueness phase transition on the infinite Δ-regular tree. Despite this clear picture for 2-spin systems, there is little known for multispin systems. We present the first analog of this in approximability results for multispin systems. The main difficulty in previous inapproximability results was analyzing the behavior of the model on random Δ-regular bipartite graphs, which served as the gadget in the reduction. To this end, one needs to understand the moments of the partition function. Our key contribution is connecting: (i) induced matrix norms, (ii) maxima of the expectation of the partition function, and (iii) attractive fixed points of the associated tree recursions (belief propagation). The view through matrix norms allows a simple and generic analysis of the second moment for any spin system on random Δ-regular bipartite graphs. This yields concentration results for any spin system in which one can analyze the maxima of the first moment. The connection to fixed points of the tree recursions enables an analysis of the maxima of the first moment for specific models of interest. For k -colorings we prove that for even k , in a tree nonuniqueness region (which corresponds to k < Δ) there is no FPRAS, unless NP = RP, to approximate the number of colorings for triangle-free Δ-regular graphs. Our proof extends to the antiferromagnetic Potts model, and, in fact, to every antiferromagnetic model under a mild condition.

Counting independent sets 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 study #BIS in the general framework of two-state spin systems in bipartite graphs. Such a system is parameterized by three numbers (beta,gamma,lambda), where beta (respectively gamma) represents the weight of an edge (or "interaction strength") whose endpoints are of the same 0 (respectively 1) spin, and lambda is the weight of a 1 vertex, also known as an "external field". By convention, the edge weight with unequal 0/1 end points and the vertex weight with spin 0 are both normalized to 1. The partition function of the special case beta=1, gamma=0, and lambda=1 counts the number of independent sets. We define two notions, nearly-independent phase-correlated spins and symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any two-spin system on bipartite graphs supporting these two notions. As a consequence, 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. This result extends to the hard-core model and to other anti-ferromagnetic two-spin models. In particular, for all antiferromagnetic two-spin systems, namely those satisfying beta*gamma<1, we prove that when the infinite (Delta-1)-ary tree lies in the non-uniqueness region then it is #BIS-hard to approximate the partition function on bipartite graphs of maximum degree Delta, except for the case beta=gamma and lambda=1. The exceptional case is precisely the antiferromagnetic Ising model without an external field, and we show that it has an FPRAS on bipartite graphs. Our inapproximability results match the approximability results of Li et al., who presented an FPTAS for general graphs of maximum degree Delta when the parameters lie in the uniqueness region.

Recent results establish for the hard-core model (and more generally for 2-spin antiferromagnetic systems) that the computational complexity of approximating the partition function on graphs of maximum degree D undergoes a phase transition that coincides with the uniqueness/non-uniqueness phase transition on the infinite D-regular tree. For the ferromagnetic Potts model we investigate whether analogous hardness results hold. Goldberg and Jerrum showed that approximating the partition function of the ferromagnetic Potts model is at least as hard as approximating the number of independent sets in bipartite graphs, so-called #BIS-hardness. We improve this hardness result by establishing it for bipartite graphs of maximum degree D. To this end, we first present a detailed picture for the phase diagram for the infinite D-regular tree, giving a refined picture of its first-order phase transition and establishing the critical temperature for the coexistence of the disordered and ordered phases. We then prove for all temperatures below this critical temperature (corresponding to the region where the ordered phase "dominates") that it is #BIS-hard to approximate the partition function on bipartite graphs of maximum degree D. The #BIS-hardness result uses random bipartite regular graphs as a gadget in the reduction. The analysis of these random graphs relies on recent results establishing connections between the maxima of the expectation of their partition function, attractive fixpoints of the associated tree recursions, and induced matrix norms. In this paper we extend these connections to random regular graphs for all ferromagnetic models. Using these connections, we establish the Bethe prediction for every ferromagnetic spin system on random regular graphs, which says roughly that the expectation of the log of the partition function Z is the same as the log of the expectation of Z. As a further consequence of our results, we prove for the ferromagnetic Potts model that the Swendsen-Wang algorithm is torpidly mixing (i.e., exponentially slow convergence to its stationary distribution) on random D-regular graphs at the critical temperature for sufficiently large q.

A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree Δ undergoes a phase transition that coincides with the statistical physics uniqueness/non-uniqueness phase transition on the infinite Δ-regular tree. Despite this clear picture for 2-spin systems, there is little known for multi-spin systems. We present the first analog of the above inapproximability results for multi-spin systems.