Approximation via Correlation Decay when Strong Spatial Mixing Fails* Ivona Bezakovat Andreas Galanist Leslie Ann Goldbergf Heng Guos Daniel Stefankovic 23 January 2019 Abstract Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approxima- tion of the partition function of anti-ferromagnetic two-spin models. Previous analyses of correlation-decay algorithms implicitly depended on the occur- rence of strong spatial miring.This,roughly,means that one uses worst-case analysis of the recursive procedure that creates the sub-instances.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 amortise against certain "bad"instances that are created as the recursion proceeds.This enables us to show correlation decay and to obtain an 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 A and with a lower bound k on the arity of hyperedges.Liu and Lin gave an FPTAS for k >2 and A <5(lack of strong spatial mixing was the obstacle preventing this algorithm from being generalised to A=6).Our technique gives a tight result for A =6,showing that there is an FPTAS for k >3 and A 6.The best previously-known approximation scheme for A=6 is the Markov-chain simulation based FPRAS of Bordewich,Dyer and Karpinski,which only works for k>8. Our technique also applies for larger values of k,giving an FPTAS for k >A.This bound is not substantially stronger than existing randomised results in the literature. Nevertheless,it gives the first deterministic approximation scheme in this regime.More- over,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 *This work was done in part while the authors were visiting the Simons Institute for the Theory of Com- puting. Department of Computer Science,Rochester Institute of Technology,Rochester,NY,USA.Research sup- ported by NSF grant CCF-1319987. Department of Computer Science,University of Oxford,Wolfson Building,Parks Road,Oxford,OX1 3QD, UK.The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)ERC grant agreement no.334828. The paper reflects only the authors'views and not the views of the ERC or the European Commission.The European Union is not liable for any use that may be made of the information contained therein. SSchool of Informatics,University of Edinburgh,Informatics Forum,Edinburgh,EH8 9AB,UK. Department of Computer Science,University of Rochester,Rochester,NY 14627.Research supported by NSF grant CCF-1563757
Approximation via Correlation Decay when Strong Spatial Mixing Fails∗ Ivona BezákovᆠAndreas Galanis‡ Leslie Ann Goldberg‡ Heng Guo§ Daniel Štefankovič¶ 23 January 2019 Abstract 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 anti-ferromagnetic two-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 sub-instances. 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 amortise against certain “bad” instances that are created as the recursion proceeds. This enables us to show correlation decay and to obtain an 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 ∆ and with a lower bound k on the arity of hyperedges. Liu and Lin gave an FPTAS for k ≥ 2 and ∆ ≤ 5 (lack of strong spatial mixing was the obstacle preventing this algorithm from being generalised to ∆ = 6). Our technique gives a tight result for ∆ = 6, showing that there is an FPTAS for k ≥ 3 and ∆ ≤ 6. The best previously-known approximation scheme for ∆ = 6 is the Markov-chain simulation based FPRAS of Bordewich, Dyer and Karpinski, which only works for k ≥ 8. Our technique also applies for larger values of k, giving an FPTAS for k ≥ ∆. This bound is not substantially stronger than existing randomised 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 ∗This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing. †Department of Computer Science, Rochester Institute of Technology, Rochester, NY, USA. Research supported by NSF grant CCF-1319987. ‡Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK. The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) ERC grant agreement no. 334828. The paper reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. §School of Informatics, University of Edinburgh, Informatics Forum, Edinburgh, EH8 9AB, UK. ¶Department of Computer Science, University of Rochester, Rochester, NY 14627. Research supported by NSF grant CCF-1563757. 1
counting dominating sets of bounded-degree graphs(without the regularity restriction)is NP-hard. 1 Introduction We develop a new method for analysing correlation decays in spin systems.In particular,we take the shape of instances in the computation tree into consideration and we amortise against certain "bad"instances that are created as the recursion proceeds.This enables us to show correlation decay and to obtain an FPTAS even when strong spatial mixing fails.To the best of our knowledge,strong spatial mixing is a requirement for all previous correlation-decay based algorithms.To illustrate our technique,we focus on the computational complexity of approximately counting independent sets in hypergraphs,or equivalently on counting the satisfying assignments of monotone CNF formulas. The problem of counting independent sets in graphs(denoted #IS)is extensively studied. A beautiful connection has been established,showing that approximately counting indepen- dent sets in graphs of maximum degree A undergoes a computational transition which coin- cides with the uniqueness phase transition from statistical physics on the infinite A-regular tree.The computational transition can be described as follows.Weitz [22]designed an FP- TAS for counting independent sets on graphs with maximum degree at most A =5.On the other hand,Sly [19]proved that there is no FPRAS for approximately counting independent sets on graphs with maximum degree at most A =6(unless NP =RP).The same connection has been established in the more general context of approximating the partition function of the hard-core model [22,16,19,4,6,20]and in the even broader context of approximating the partition functions of generic antiferromagnetic 2-spin models [18,6,20,11](which includes, for example,the antiferromagnetic Ising model).As a consequence,the boundary for the existence of efficient approximation algorithms for these models has been mapped out. Approximate counting via correlation decay is the core technique in the algorithmic devel- opments which enabled the sharp delineation of the computational phase transition.Another standard approach for approximate counting,namely Markov chain Monte Carlo (MCMC) simulation,is also conjectured to work up to the uniqueness threshold,but the current analy- sis tools that we have do not seem to be powerful enough to show that.For example,sampling independent sets via MCMC simulation is known to have fast mixing only for graphs with degree at most 4 [14,3],rather than obtaining the true threshold of 5. In this work,we consider counting independent sets in hypergraphs with upper-bounded vertex degree,and lower-bounded hyperedge size.A hypergraph H=(V,F)consists of a vertex set V and a set F of hyperedges,each of which is a subset of V.A hypergraph is said to be k-uniform if every hyperedge contains exactly k vertices.Thus,a 2-uniform hypergraph is the same as a graph.We will consider the more general case where each hyperedge has arity at least k,rather than exactly k. An independent set in a hypergraph H is a subset of vertices that does not contain a hyperedge as a subset.We will be interested in computing ZH,which is the total number of independent sets in H(also referred to as the partition function of H).Formally,the problem of counting independent sets has two parameters-a degree upper bound A and a INote that there are non-monotonic examples of antiferromagnetic 2-spin systems where the boundary is more complicated because the uniqueness threshold fails to be monotonic in A [10.However,this can be cleared up by stating the uniqueness condition as uniqueness for all d A.See [10,11]for details
counting dominating sets of bounded-degree graphs (without the regularity restriction) is NP-hard. 1 Introduction We develop a new method for analysing correlation decays in spin systems. In particular, we take the shape of instances in the computation tree into consideration and we amortise against certain “bad” instances that are created as the recursion proceeds. This enables us to show correlation decay and to obtain an FPTAS even when strong spatial mixing fails. To the best of our knowledge, strong spatial mixing is a requirement for all previous correlation-decay based algorithms. To illustrate our technique, we focus on the computational complexity of approximately counting independent sets in hypergraphs, or equivalently on counting the satisfying assignments of monotone CNF formulas. The problem of counting independent sets in graphs (denoted #IS) is extensively studied. A beautiful connection has been established, showing that approximately counting independent sets in graphs of maximum degree ∆ undergoes a computational transition which coincides with the uniqueness phase transition from statistical physics on the infinite ∆-regular tree. The computational transition can be described as follows. Weitz [22] designed an FPTAS for counting independent sets on graphs with maximum degree at most ∆ = 5. On the other hand, Sly [19] proved that there is no FPRAS for approximately counting independent sets on graphs with maximum degree at most ∆ = 6 (unless NP = RP). The same connection has been established in the more general context of approximating the partition function of the hard-core model [22, 16, 19, 4, 6, 20] and in the even broader context of approximating the partition functions of generic antiferromagnetic 2-spin models [18, 6, 20, 11] (which includes, for example, the antiferromagnetic Ising model). As a consequence, the boundary for the existence of efficient approximation algorithms for these models has been mapped out1 . Approximate counting via correlation decay is the core technique in the algorithmic developments which enabled the sharp delineation of the computational phase transition. Another standard approach for approximate counting, namely Markov chain Monte Carlo (MCMC) simulation, is also conjectured to work up to the uniqueness threshold, but the current analysis tools that we have do not seem to be powerful enough to show that. For example, sampling independent sets via MCMC simulation is known to have fast mixing only for graphs with degree at most 4 [14, 3], rather than obtaining the true threshold of 5. In this work, we consider counting independent sets in hypergraphs with upper-bounded vertex degree, and lower-bounded hyperedge size. A hypergraph H = (V, F) consists of a vertex set V and a set F of hyperedges, each of which is a subset of V . A hypergraph is said to be k-uniform if every hyperedge contains exactly k vertices. Thus, a 2-uniform hypergraph is the same as a graph. We will consider the more general case where each hyperedge has arity at least k, rather than exactly k. An independent set in a hypergraph H is a subset of vertices that does not contain a hyperedge as a subset. We will be interested in computing ZH, which is the total number of independent sets in H (also referred to as the partition function of H). Formally, the problem of counting independent sets has two parameters — a degree upper bound ∆ and a 1Note that there are non-monotonic examples of antiferromagnetic 2-spin systems where the boundary is more complicated because the uniqueness threshold fails to be monotonic in ∆ [10]. However, this can be cleared up by stating the uniqueness condition as uniqueness for all d ≤ ∆. See [10, 11] for details. 2
lower bound k on the arity of hyperedges.The problem is defined as follows.2 Name #HyperlndSet(k,A) Instance A hypergraph H with maximum degree at most A where each hyperedge has car- dinality (arity)at least k. Output The number ZH of independent sets in H. Previously,#HyperlndSet(,A)has been studied using the MCMC technique by Border- wich,Dyer,and Karpinski [1,2](see also [3]).They give an FPRAS for all k >A+2 >5 and for k >2 and A =3.Despite equipping path coupling with optimized metrics obtained using linear programming,these bounds are not tight for small k.Liu and Lu [12]showed that there exists an FPTAS for all k>2 and A 5 using the correlation decay technique. Thus,the situation seems to be similar to the graph case-given the analysis tools that we have,correlation-decay brings us closer to the truth than the best-tuned analysis of MCMC simulation algorithms.On the other hand,the technique of Liu and Lu [12]does not extend beyond A =5.To explain the reason why it does not,we need to briefly describe the correlation-decay-based algorithm framework introduced by Weitz [22].The main idea is to build a recursive procedure for computing the marginal probability that any given vertex is in the independent set.The recursion works by examining sub-instances with "boundary conditions"which require certain vertices to be in,or out,of the independent set.The recur- sion structure is called a "computation tree".Nodes of the tree correspond to intermediate instances,and boundary conditions are different in different branches.The computation tree allows one to compute the marginal probability exactly but the time needed to do so may be exponentially large since,in general,the tree is exponentially large.Typically,an approx- imate marginal probability is obtained by truncating the computation tree to logarithmic depth so that the(approximation)algorithm runs in polynomial time.If the correlation be- tween boundary conditions at the leaves of the(truncated)computation tree and the marginal probability at the root decays exponentially with respect to the depth,then the error incurred from the truncation is small and the algorithm succeeds in obtaining a close approximation. All previous instantiations under this framework require a property called strong spatial miring (SSM)3,which roughly states that,conditioned on any boundary condition on inter- mediate nodes,the correlation decays.In other words,SSM guards against the worst-case boundary conditions that might be created by the recursive procedure. Let the (A-1)-ary k-uniform hypertree T&,A be the recursively-defined hypergraph in which each vertex has A-1 "descending"hyperedges,each containing k-1 new vertices. Observation1.Letk≥2.For△≥6，strong spatial miring does not hold on Tk.△. Observation 1 follows from the fact that the infinite (A-1)-ary tree T2.A can be embedded in the hypertree TkA,and from well-known facts about the phase transition on T2.A. Observation 1 prevents the generalisation of Liu and Lu's algorithm [12]so that it applies for A 6.even with an edge-size lower bound k.The problem is that the construction of the computation tree involves constructing intermediate instances in which the arity of a hyperedge can be as small as 2.So,even if we start with a k-uniform hypergraph,the 2Equivalently,one may think of this problem as the problem of counting satisfying assignments of a mono- tone CNF formulas,where vertices are variables and hyperedges are clauses.Being out of the independent set (as a vertex)corresponds to being true (as a variable). 3See Section 2.1 for a definition. 3
lower bound k on the arity of hyperedges. The problem is defined as follows.2 Name #HyperIndSet(k, ∆). Instance A hypergraph H with maximum degree at most ∆ where each hyperedge has cardinality (arity) at least k. Output The number ZH of independent sets in H. Previously, #HyperIndSet(k, ∆) has been studied using the MCMC technique by Borderwich, Dyer, and Karpinski [1, 2] (see also [3]). They give an FPRAS for all k ≥ ∆ + 2 ≥ 5 and for k ≥ 2 and ∆ = 3. Despite equipping path coupling with optimized metrics obtained using linear programming, these bounds are not tight for small k. Liu and Lu [12] showed that there exists an FPTAS for all k ≥ 2 and ∆ ≤ 5 using the correlation decay technique. Thus, the situation seems to be similar to the graph case — given the analysis tools that we have, correlation-decay brings us closer to the truth than the best-tuned analysis of MCMC simulation algorithms. On the other hand, the technique of Liu and Lu [12] does not extend beyond ∆ = 5. To explain the reason why it does not, we need to briefly describe the correlation-decay-based algorithm framework introduced by Weitz [22]. The main idea is to build a recursive procedure for computing the marginal probability that any given vertex is in the independent set. The recursion works by examining sub-instances with “boundary conditions” which require certain vertices to be in, or out, of the independent set. The recursion structure is called a “computation tree”. Nodes of the tree correspond to intermediate instances, and boundary conditions are different in different branches. The computation tree allows one to compute the marginal probability exactly but the time needed to do so may be exponentially large since, in general, the tree is exponentially large. Typically, an approximate marginal probability is obtained by truncating the computation tree to logarithmic depth so that the (approximation) algorithm runs in polynomial time. If the correlation between boundary conditions at the leaves of the (truncated) computation tree and the marginal probability at the root decays exponentially with respect to the depth, then the error incurred from the truncation is small and the algorithm succeeds in obtaining a close approximation. All previous instantiations under this framework require a property called strong spatial mixing (SSM)3 , which roughly states that, conditioned on any boundary condition on intermediate nodes, the correlation decays. In other words, SSM guards against the worst-case boundary conditions that might be created by the recursive procedure. Let the (∆ − 1)-ary k-uniform hypertree Tk,∆ be the recursively-defined hypergraph in which each vertex has ∆ − 1 “descending” hyperedges, each containing k − 1 new vertices. Observation 1. Let k ≥ 2. For ∆ ≥ 6, strong spatial mixing does not hold on Tk,∆. Observation 1 follows from the fact that the infinite (∆−1)-ary tree T2,∆ can be embedded in the hypertree Tk,∆, and from well-known facts about the phase transition on T2,∆. Observation 1 prevents the generalisation of Liu and Lu’s algorithm [12] so that it applies for ∆ ≥ 6, even with an edge-size lower bound k. The problem is that the construction of the computation tree involves constructing intermediate instances in which the arity of a hyperedge can be as small as 2. So, even if we start with a k-uniform hypergraph, the 2Equivalently, one may think of this problem as the problem of counting satisfying assignments of a monotone CNF formulas, where vertices are variables and hyperedges are clauses. Being out of the independent set (as a vertex) corresponds to being true (as a variable). 3See Section 2.1 for a definition. 3
computation tree will contain instances with small hyperedges.Without strong spatial mixing, these small hyperedges cause problems in the analysis.Lu,Yang and Zhang [13]discuss this problem and say "How to avoid this effect is a major open question whose solution may have applications in many other problems."This question motivates our work. To overcome this difficulty,we introduce a new amortisation technique in the analysis. Since lack of correlation decay is caused primarily by the presence of small-arity hyperedges within the intermediate instances,we keep track of such hyperedges.Thus,we track not only the correlation,but also combinatorial properties of the intermediate instances in the computation tree.Using this idea,we obtain the following result. Theorem 2.There is an FPTAS for #HyperlndSet(3,6). Note that #HyperlndSet(2,6)is NP-hard to approximate due to [19],so our result is tight for A =6.This also shows that A=6 is the first case where the complexity of approximately counting independent sets differs on hypergraphs and graphs,as for A <5 both admit an FPTAS [12].Moreover,Theorem 2 is stronger than the best MCMC algorithm [2]when △=6as[2 only works for k≥8. We also apply our technique to large k. Theorem3.Let k and△be two integers such that k≥△and△≥200.Then there is an FPTAS for the problem #HyperlndSet(k,A). In the large k case,our result is not substantially stronger than that obtained by analysis of the MCMC algorithm[2](k≥△rather than k≥△+2)but it is incomparable since our algorithm is deterministic rather than randomised.Perhaps more importantly,the bound k >A allows us to connect the problem of counting independent sets in hypergraphs with the problem of counting dominating sets in A-regular graphs and show that the latter admits an FPTAS when A is sufficiently large.Recall that a dominating set in a graph G is a subset S of the vertices such that every vertex not in S is adjacent to at least one vertex in S.We then consider the following problem. Name#RegDomSet(△) Instance A A-regular graph G. Output The number of dominating sets in G. Our theorems have the following corollary. Corollary4.For all po.sitive integers△satisfying either△≤5or△≥l99,there is an FPTAS for the problem #RegDomSet(A). We remark that Corollary 4 cannot be obtained using the result of [2],i.e.,the seemingly small difference between k≥△andk≥△+2 does matter in deriving Corollary4fom Theorems 2 and 3.We should also emphasise that it is necessary to consider A-regular graphs as inputs to the dominating set problem,since otherwise for graphs of maximum degree A (not necessarily regular),we show that the problem is NP-hard to approximate for A >18 (Theorem 52).It is relevant to remark here that we believe that Corollary 4 should hold for all△；to do this,it would be sufficient to remove the restriction△≥200 from Theorem 3.Note that,while we do not know how to remove the restriction,it would at least be possible to improve"200"to some smaller number.However,we have chosen to stick
computation tree will contain instances with small hyperedges. Without strong spatial mixing, these small hyperedges cause problems in the analysis. Lu, Yang and Zhang [13] discuss this problem and say “How to avoid this effect is a major open question whose solution may have applications in many other problems.” This question motivates our work. To overcome this difficulty, we introduce a new amortisation technique in the analysis. Since lack of correlation decay is caused primarily by the presence of small-arity hyperedges within the intermediate instances, we keep track of such hyperedges. Thus, we track not only the correlation, but also combinatorial properties of the intermediate instances in the computation tree. Using this idea, we obtain the following result. Theorem 2. There is an FPTAS for #HyperIndSet(3, 6). Note that #HyperIndSet(2, 6) is NP-hard to approximate due to [19], so our result is tight for ∆ = 6. This also shows that ∆ = 6 is the first case where the complexity of approximately counting independent sets differs on hypergraphs and graphs, as for ∆ ≤ 5 both admit an FPTAS [12]. Moreover, Theorem 2 is stronger than the best MCMC algorithm [2] when ∆ = 6 as [2] only works for k ≥ 8. We also apply our technique to large k. Theorem 3. Let k and ∆ be two integers such that k ≥ ∆ and ∆ ≥ 200. Then there is an FPTAS for the problem #HyperIndSet(k, ∆). In the large k case, our result is not substantially stronger than that obtained by analysis of the MCMC algorithm [2] (k ≥ ∆ rather than k ≥ ∆ + 2) but it is incomparable since our algorithm is deterministic rather than randomised. Perhaps more importantly, the bound k ≥ ∆ allows us to connect the problem of counting independent sets in hypergraphs with the problem of counting dominating sets in ∆-regular graphs and show that the latter admits an FPTAS when ∆ is sufficiently large. Recall that a dominating set in a graph G is a subset S of the vertices such that every vertex not in S is adjacent to at least one vertex in S. We then consider the following problem. Name #RegDomSet(∆). Instance A ∆-regular graph G. Output The number of dominating sets in G. Our theorems have the following corollary. Corollary 4. For all positive integers ∆ satisfying either ∆ ≤ 5 or ∆ ≥ 199, there is an FPTAS for the problem #RegDomSet(∆). We remark that Corollary 4 cannot be obtained using the result of [2], i.e., the seemingly small difference between k ≥ ∆ and k ≥ ∆ + 2 does matter in deriving Corollary 4 from Theorems 2 and 3. We should also emphasise that it is necessary to consider ∆-regular graphs as inputs to the dominating set problem, since otherwise for graphs of maximum degree ∆ (not necessarily regular), we show that the problem is NP-hard to approximate for ∆ ≥ 18 (Theorem 52). It is relevant to remark here that we believe that Corollary 4 should hold for all ∆; to do this, it would be sufficient to remove the restriction ∆ ≥ 200 from Theorem 3. Note that, while we do not know how to remove the restriction, it would at least be possible to improve “200” to some smaller number. However, we have chosen to stick 4
with "200"in order to keep the proof accessible.We explain next the difficulties in obtaining Theorems 2 and 3. The main technical difficulty in correlation-decay analysis is bounding a function that we call the "decay rate".This boils down to solving an optimisation problem with (k- 1)(A-1)variables.In previous work(e.g.[17]),this optimisation has been solved using a so- called "symmetrization"argument,which reduces the problem to a univariate optimisation via convexity.However,the many variables represent different branches in the computation tree. Since our analysis takes the shape of intermediate instances in the tree into consideration.the symmetrization argument does not work for us,and different branches take different values at the maximum.This problem is compounded by the fact that the shape of the sub-tree consisting of "bad"intermediate instances is heavily lopsided,and the assignment of variables achieving the maximum is far from uniform.Given these problems,there does not seem to be a clean solution to the optimisation in our analysis.Instead of optimizing,we give an upper bound on the maximum decay rate.In Theorem 2,as k and A are small,the number of variables is manageable,and our bounds are much sharper than those in Theorem 3.On the other hand,because of this,the proof of Theorem 3 is much more accessible,and we will use Theorem 3 as a running example to demonstrate our technique. We also provide some insight on the hardness side.Recall that for graphs it is NP-hard to approximate #IS beyond the uniqueness threshold (A =6)[19].4 We prove that it is NP-hard to approximate #HyperlndSet(6,22)(Corollary 50).In contrast,we show that uniqueness holds on the 6-uniform A-regular hypertree iff A 28 (Corollary 59).Thus,efficient ap- proximation schemes cease to exist well below the uniqueness threshold on the hypertree.In fact,we show that this discrepancy grows exponentially in k:for large k,it is NP-hard to approximate #HyperlndSet(,A)when A>5.2/2(Theorem 49 and Corollary 51),despite the fact that uniqueness holds on the hypertree for all A <2/(2k)(Lemma 60).Theorem 49 follows from a rather standard reduction to the hard-core model on graphs.Nevertheless,it demonstrates that the computational-threshold phenomena in the hypergraph case (k>2) are substantially different from those in the graph case(k=2). As mentioned earlier,there are models where efficient(randomised)approximation schemes exist (based on MCMC simulation)even though SSM does not hold.In fact,this can happen even when uniqueness does not hold.A striking example is the ferromagnetic Ising model (with external field).As [18]shows,there are parameter regimes where uniqueness holds but strong spatial mixing fails.It is easy to modify the parameters so that even uniqueness fails.Nevertheless,Jerrum and Sinclair [9]gave an MCMC-based FPRAS that applies for all parameters and for general graphs (with no degree bounds).It is still an open question to give a correlation decay based FPTAS for the ferromagnetic Ising model. 1.1 Note added in revision-recent work After our work,Hermon,Sly,and Zhang [8]have shown that the Glauber dynamics for sampling independent sets on n-vertex k-uniform hypergraphs has mixing time O(n log n), if A <c2k/2 for some constant c.Combined with our hardness result,Corollary 51,this establishes a sharp computational complexity phase transition,up to constants.Moreover, Moitra [15]has given a deterministic algorithm for approximately counting and sampling the satisfying assignments of k-CNF formulas,provided that the variable degree A/60 4For graphs the uniqueness and SSM thresholds coincide,but for hypergraphs they differ. 5
with “200” in order to keep the proof accessible. We explain next the difficulties in obtaining Theorems 2 and 3. The main technical difficulty in correlation-decay analysis is bounding a function that we call the “decay rate”. This boils down to solving an optimisation problem with (k − 1)(∆ −1) variables. In previous work (e.g. [17]), this optimisation has been solved using a socalled “symmetrization” argument, which reduces the problem to a univariate optimisation via convexity. However, the many variables represent different branches in the computation tree. Since our analysis takes the shape of intermediate instances in the tree into consideration, the symmetrization argument does not work for us, and different branches take different values at the maximum. This problem is compounded by the fact that the shape of the sub-tree consisting of “bad” intermediate instances is heavily lopsided, and the assignment of variables achieving the maximum is far from uniform. Given these problems, there does not seem to be a clean solution to the optimisation in our analysis. Instead of optimizing, we give an upper bound on the maximum decay rate. In Theorem 2, as k and ∆ are small, the number of variables is manageable, and our bounds are much sharper than those in Theorem 3. On the other hand, because of this, the proof of Theorem 3 is much more accessible, and we will use Theorem 3 as a running example to demonstrate our technique. We also provide some insight on the hardness side. Recall that for graphs it is NP-hard to approximate #IS beyond the uniqueness threshold (∆ = 6) [19].4 We prove that it is NP-hard to approximate #HyperIndSet(6, 22) (Corollary 50). In contrast, we show that uniqueness holds on the 6-uniform ∆-regular hypertree iff ∆ ≤ 28 (Corollary 59). Thus, efficient approximation schemes cease to exist well below the uniqueness threshold on the hypertree. In fact, we show that this discrepancy grows exponentially in k: for large k, it is NP-hard to approximate #HyperIndSet(k, ∆) when ∆ ≥ 5 · 2 k/2 (Theorem 49 and Corollary 51), despite the fact that uniqueness holds on the hypertree for all ∆ ≤ 2 k/(2k) (Lemma 60). Theorem 49 follows from a rather standard reduction to the hard-core model on graphs. Nevertheless, it demonstrates that the computational-threshold phenomena in the hypergraph case (k > 2) are substantially different from those in the graph case (k = 2). As mentioned earlier, there are models where efficient (randomised) approximation schemes exist (based on MCMC simulation) even though SSM does not hold. In fact, this can happen even when uniqueness does not hold. A striking example is the ferromagnetic Ising model (with external field). As [18] shows, there are parameter regimes where uniqueness holds but strong spatial mixing fails. It is easy to modify the parameters so that even uniqueness fails. Nevertheless, Jerrum and Sinclair [9] gave an MCMC-based FPRAS that applies for all parameters and for general graphs (with no degree bounds). It is still an open question to give a correlation decay based FPTAS for the ferromagnetic Ising model. 1.1 Note added in revision — recent work After our work, Hermon, Sly, and Zhang [8] have shown that the Glauber dynamics for sampling independent sets on n-vertex k-uniform hypergraphs has mixing time O(n log n), if ∆ ≤ c2 k/2 for some constant c. Combined with our hardness result, Corollary 51, this establishes a sharp computational complexity phase transition, up to constants. Moreover, Moitra [15] has given a deterministic algorithm for approximately counting and sampling the satisfying assignments of k-CNF formulas, provided that the variable degree ∆ ≲ 2 k/60 . 4For graphs the uniqueness and SSM thresholds coincide, but for hypergraphs they differ. 5