On the hardness of sampling independent sets beyond the tree threshold

DOI10.1007/s00440-007-0131-9zbMath1165.60028arXivmath/0701471MaRDI 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

60J22: Computational methods in Markov chains

68Q25: Analysis of algorithms and problem complexity

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

Related Items

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

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)\)