Approximation via Correlation Decay When Strong Spatial Mixing Fails

DOI10.1137/16M1083906zbMath1422.68270OpenAlexW2962726369WikidataQ128155964 ScholiaQ128155964MaRDI QIDQ4634020

Heng Guo, Ivona Bezáková, Daniel Štefanković, Leslie Ann Goldberg, Andreas Galanis

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1083906

zbMATH Keywords

approximate countingcorrelation decayhypergraph independent set

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (4)

Counting Solutions to Random CNF Formulas ⋮ Inapproximability of counting independent sets in linear hypergraphs ⋮ Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems ⋮ Counting Hypergraph Colorings in the Local Lemma Regime

Cites Work

• Approximately counting locally-optimal structures
• The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
• Counting in two-spin models on \(d\)-regular graphs
• On the hardness of sampling independent sets beyond the tree threshold
• Cylindrical algebraic decomposition using validated numerics
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Improved inapproximability results for counting independent sets in the hard-core model
• Counting independent sets up to the tree threshold
• Polynomial-Time Approximation Algorithms for the Ising Model
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Stopping Times, Metrics and Approximate Counting
• FPTAS for Hardcore and Ising Models on Hypergraphs
• Sampling in Potts Model on Sparse Random Graphs
• Fast convergence of the Glauber dynamics for sampling independent sets
• On Markov Chains for Independent Sets
• Approximate counting, the Lovasz local lemma, and inference in graphical models
• Rapid mixing of hypergraph independent sets
• FPTAS for Counting Monotone CNF
• Spatial mixing and the connective constant: Optimal bounds
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Correlation Decay up to Uniqueness in Spin Systems
• Approximate Counting via Correlation Decay in Spin Systems

This page was built for publication: Approximation via Correlation Decay When Strong Spatial Mixing Fails