Approximate counting via correlation decay in spin systems
From MaRDI portal
Abstract: We give the first deterministic fully polynomial-time approximation scheme (FPTAS) for computing the partition function of a two-state spin system on an arbitrary graph, when the parameters of the system satisfy the uniqueness condition on infinite regular trees. This condition is of physical significance and is believed to be the right boundary between approximable and inapproximable. The FPTAS is based on the correlation decay technique introduced by Bandyopadhyay and Gamarnik [SODA 06] and Weitz [STOC 06]. The classic correlation decay is defined with respect to graph distance. Although this definition has natural physical meanings, it does not directly support an FPTAS for systems on arbitrary graphs, because for graphs with unbounded degrees, the local computation that provides a desirable precision by correlation decay may take super-polynomial time. We introduce a notion of computationally efficient correlation decay, in which the correlation decay is measured in a refined metric instead of graph distance. We use a potential method to analyze the amortized behavior of this correlation decay and establish a correlation decay that guarantees an inverse-polynomial precision by polynomial-time local computation. This gives us an FPTAS for spin systems on arbitrary graphs. This new notion of correlation decay properly reflects the algorithmic aspect of the spin systems, and may be used for designing FPTAS for other counting problems.
Recommendations
Cites work
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- A deterministic polynomial-time approximation scheme for counting knapsack solutions
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- An approximation trichotomy for Boolean \#CSP
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Complexity of generalized satisfiability counting problems
- Correlation decay and deterministic FPTAS for counting list-colorings of a graph
- Counting and sampling \(H\)-colourings
- Counting independent sets up to the tree threshold
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Coupling with the stationary distribution and improved sampling for colorings and independent sets
- Fast mixing for independent sets, colorings, and other models on trees
- Gibbs measures and phase transitions
- Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
- Holant problems and counting CSP
- scientific article; zbMATH DE number 5485444 (Why is no real title available?)
- scientific article; zbMATH DE number 3951995 (Why is no real title available?)
- scientific article; zbMATH DE number 1342087 (Why is no real title available?)
- scientific article; zbMATH DE number 1545676 (Why is no real title available?)
- scientific article; zbMATH DE number 1559584 (Why is no real title available?)
- scientific article; zbMATH DE number 2151251 (Why is no real title available?)
- Improved bounds for sampling colorings
- Inapproximability of the Tutte polynomial of a planar graph
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- On counting homomorphisms to directed acyclic graphs
- On Counting Independent Sets in Sparse Graphs
- On Markov Chains for Independent Sets
- On Markov chains for randomly H-coloring a graph
- On the complexity of \#CSP
- On the hardness of sampling independent sets beyond the tree threshold
- Path coupling using stopping times and counting independent sets and colorings in hypergraphs
- Polynomial-Time Approximation Algorithms for the Ising Model
- Prescribing a System of Random Variables by Conditional Distributions
- Random generation of combinatorial structures from a uniform distribution
- Randomly coloring constant degree graphs
- Randomly coloring graphs of girth at least five
- Randomly coloring graphs with lower bounds on girth and maximum degree
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Slow mixing of Glauber dynamics for the hard-core model on the hypercube
- The complexity of approximating bounded-degree Boolean \#CSP
- The complexity of partition functions
- The Complexity of the Counting Constraint Satisfaction Problem
- The Complexity of Weighted Boolean #CSP
- The computational complexity of two‐state spin systems
- The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
- The mixing time of Glauber dynamics for coloring regular trees
- Torpid mixing of local Markov chains on 3-colorings of the discrete torus
- Torpid mixing of simulated tempering on the Potts model
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
Cited in
(30)- Counting hypergraph matchings up to uniqueness threshold
- Approximating partition functions of the two-state spin system
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Spatial mixing and the connective constant: optimal bounds
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Improved FPTAS for multi-spin systems
- Correlation decay and deterministic FPTAS for counting list-colorings of a graph
- Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
- Approximation via correlation decay when strong spatial mixing fails
- FPTAS for hardcore and Ising models on hypergraphs
- Approximation via Correlation Decay When Strong Spatial Mixing Fails
- Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- FPTAS for weighted Fibonacci gates and its applications
- Correlation decay in random decision networks
- Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems
- FPTAS for counting monotone CNF
- Spatial mixing and the connective constant: optimal bounds
- A simple FPTAS for counting edge covers
- Approximate counting via correlation decay on planar graphs
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
- Approximability of the complementarily symmetric Holant problems on cubic graphs
- Correlation decay and the absence of zeros property of partition functions
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Correlation decay and partition function zeros: algorithms and phase transitions
- Bounded degree nonnegative counting CSP
- An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
- An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
This page was built for publication: Approximate counting via correlation decay in spin systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743448)
