On the hardness of sampling independent sets beyond the tree threshold

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

Elchanan Mossel, Nicholas C. Wormald, Dror Weitz

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

Branching Process Approach for 2-Sat Thresholds, Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Gibbs rapidly samples colorings of \(G(n, d/n)\), \(\#\)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, Exact thresholds for Ising-Gibbs samplers on general 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, 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)\)