Approximate Counting via Correlation Decay in Spin Systems
From MaRDI portal
Publication:5743448
zbMath1422.68301arXiv1109.0604MaRDI QIDQ5743448
Yitong Yin, Pinyan Lu, Liang Li
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1109.0604
Analysis of algorithms (68W40) Enumeration in graph theory (05C30) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Distance in graphs (05C12) Approximation algorithms (68W25)
Related Items
Spatial mixing and the connective constant: optimal bounds ⋮ \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region ⋮ Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction ⋮ Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ Approximability of the complementarily symmetric Holant problems on cubic graphs ⋮ 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 ⋮ Counting hypergraph matchings up to uniqueness threshold ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs ⋮ Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes ⋮ Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- An approximation trichotomy for Boolean \#CSP
- On the hardness of sampling independent sets beyond the tree threshold
- Random generation of combinatorial structures from a uniform distribution
- Gibbs measures and phase transitions
- Counting and sampling \(H\)-colourings
- Complexity of generalized satisfiability counting problems
- Inapproximability of the Tutte polynomial of a planar graph
- The complexity of partition functions
- On Markov Chains for Randomly H-Coloring a Graph
- Improved bounds for sampling colorings
- Randomly coloring constant degree graphs
- On the complexity of #CSP
- Improved inapproximability results for counting independent sets in the hard-core model
- A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
- Counting independent sets up to the tree threshold
- Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus
- The mixing time of Glauber dynamics for coloring regular trees
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- The Complexity of Approximating Bounded-Degree Boolean #CSP
- Polynomial-Time Approximation Algorithms for the Ising Model
- On Counting Independent Sets in Sparse Graphs
- Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Randomly coloring planar graphs with fewer colors than the maximum degree
- Path coupling using stopping times and counting independent sets and colorings in hypergraphs
- The Complexity of the Counting Constraint Satisfaction Problem
- On counting homomorphisms to directed acyclic graphs
- Randomly coloring graphs of girth at least five
- Approximating the Partition Function of the Ferromagnetic Potts Model
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- The Complexity of Weighted Boolean #CSP
- The computational complexity of two‐state spin systems
- Randomly coloring graphs with lower bounds on girth and maximum degree
- Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
- The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- On Markov Chains for Independent Sets
- Holant problems and counting CSP
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- Fast mixing for independent sets, colorings, and other models on trees
- Prescribing a System of Random Variables by Conditional Distributions
- A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem
