Approximation via correlation decay when strong spatial mixing fails

DOI10.4230/LIPICS.ICALP.2016.45MaRDI QIDQ4598184zbMATH OpenFDO

Authors Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, D. Štefankovič

Publication date 19 December 2017

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

zbMATH Keywords

approximate countingcorrelation decayhypergraphsindependent sets

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Approximate counting via correlation decay in spin systems
• Approximate counting via correlation decay on planar graphs
• Counting independent sets up to the tree threshold
• Correlation decay up to uniqueness in spin systems

Cited in

(5)

• Counting hypergraph matchings up to uniqueness threshold
• Perfect sampling for Gibbs point processes using partial rejection sampling
• The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Approximate counting via correlation decay on planar graphs

This page was built for publication: Approximation via correlation decay when strong spatial mixing fails

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598184)