Improved inapproximability results for counting independent sets in the hard-core model
type: Item
instance of: scholarly article
title: Improved inapproximability results for counting independent sets in the hard-core model
zbMATH Open document ID: 1297.05177
zbMATH Open document ID: 1343.68110
DOI: 10.1007/978-3-642-22935-0_48
DOI: 10.1002/RSA.20479
author: Andreas Galanis
author: Q. Ge
author: D. Štefankovič
author: Eric Vigoda
author: Linji Yang
published in: Random Structures \& Algorithms
publication date: 2014-08-25T00:00:00Z
publication date: 2011-08-17T00:00:00Z
full work available at URL: https://arxiv.org/abs/1105.5131
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 6334117
zbMATH DE Number: 5940184
zbMATH Keywords: approximate counting
zbMATH Keywords: phase transition
zbMATH Keywords: hard-core model
MaRDI profile type: Publication
OpenAlex ID: W2105572930
OpenAlex ID: W2130723959
arXiv ID: 1105.5131
cites work: Percolation and the hard-core lattice gas model
cites work: On Counting Independent Sets in Sparse Graphs
cites work: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: Loss networks
cites work: Q3549475
cites work: Q4344223
cites work: On the hardness of sampling independent sets beyond the tree threshold
cites work: Adaptive simulated annealing: A near-optimal connection between sampling and counting
cites work: Cylindrical algebraic decomposition using validated numerics
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Counting independent sets up to the tree threshold
cites work: Q5792485
description: scientific article; zbMATH DE number 5940184
alternative label: Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model