On the hardness of sampling independent sets beyond the tree threshold

DOI10.1007/s00440-007-0131-9zbMath1165.60028arXivmath/0701471OpenAlexW2048759201MaRDI QIDQ1017883

Elchanan Mossel, Dror Weitz, Nicholas C. Wormald

Publication date: 13 May 2009

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0701471

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Analysis of algorithms and problem complexity (68Q25) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items

\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region, Phase transitions in discrete structures, A Spectral Independence View on Hard Spheres via Block Dynamics, Approximately Counting H-Colourings is $$\#\mathrm {BIS}$$-Hard, The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs, An FPTAS for the hardcore model on random regular bipartite graphs, Harnessing the Bethe free energy, Fast algorithms at low temperatures via Markov chains†, Exact thresholds for Ising-Gibbs samplers on general graphs, Unnamed Item, Unnamed Item, Unnamed Item, Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, Factor models on locally tree-like graphs, Counting Constraint Satisfaction Problems., 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, Bethe states of random factor graphs, Counting Independent Sets and Colorings on Random Regular Bipartite Graphs, Algorithms for #BIS-Hard Problems on Expander Graphs, Counting hypergraph matchings up to uniqueness threshold, Branching Process Approach for 2-Sat Thresholds, Mixing of Markov chains for independent sets on chordal graphs with bounded separators, Gibbs measures and phase transitions on sparse random graphs, Gibbs rapidly samples colorings of \(G(n, d/n)\), Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs, Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard, Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs, Approximate Counting via Correlation Decay in Spin Systems, Tunneling of the hard‐core model on finite triangular lattices, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, Unnamed Item, Polymer dynamics via cliques: new conditions for approximations, Improved inapproximability results for counting independent sets in the hard-core model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the Glauber dynamics for sampling independent sets
• Glauber dynamics on trees and hyperbolic graphs
• The Parisi formula
• The ?(2) limit in the random assignment problem
• Counting independent sets up to the tree threshold
• Polynomial-Time Approximation Algorithms for the Ising Model
• On Counting Independent Sets in Sparse Graphs
• Design of capacity-approaching irregular low-density parity-check codes
• A second threshold for the hard‐core model on a Bethe lattice
• On Markov Chains for Independent Sets
• Gibbs rapidly samples colorings of \(G(n, d/n)\)