Approximation via Correlation Decay When Strong Spatial Mixing Fails

DOI10.1137/16M1083906MaRDI QIDQ4634020zbMATH OpenOpenAlexWikidataFDO

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

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

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

Recommendations

• Approximation via correlation decay when strong spatial mixing fails
• Spatial decay of Kubo's canonical correlation functions
• Decay of correlations in random-cluster models
• Functional correlation decay and multivariate normal approximation for non-uniformly expanding maps
• Exact decay of correlations for mixtures and rotators
• Decay of correlations for slowly mixing flows
• On Normal Approximation for Strongly Mixing Random Fields
• On the decay of correlations in the generalized spherical model
• An optimal transportation approach to the decay of correlations for non-uniformly expanding maps

Cites work

• Approximate counting via correlation decay in spin systems
• Approximate counting, the Lovász local lemma, and inference in graphical models
• Approximately counting locally-optimal structures
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Correlation decay up to uniqueness in spin systems
• Counting in two-spin models on \(d\)-regular graphs
• Counting independent sets up to the tree threshold
• Cylindrical algebraic decomposition using validated numerics
• FPTAS for counting monotone CNF
• FPTAS for hardcore and Ising models on hypergraphs
• Fast convergence of the Glauber dynamics for sampling independent sets
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• On Markov Chains for Independent Sets
• On the hardness of sampling independent sets beyond the tree threshold
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Polynomial-Time Approximation Algorithms for the Ising Model
• Rapid mixing of hypergraph independent sets
• Sampling in Potts model on sparse random graphs
• Spatial mixing and the connective constant: optimal bounds
• Stopping Times, Metrics and Approximate Counting
• The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

Cited in

(11)

• Approximation via correlation decay when strong spatial mixing fails
• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• Counting hypergraph colorings in the local lemma regime
• Toward derandomizing Markov chain Monte Carlo
• Inapproximability of counting hypergraph colourings
• Approximate counting via correlation decay on planar graphs
• Counting solutions to random CNF formulas
• On the zeroes of hypergraph independence polynomials
• Variable version Lovász local lemma: a tale of two boundaries
• Counting solutions to random CNF formulas
• Inapproximability of counting independent sets in linear hypergraphs

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