Fast algorithms at low temperatures via Markov chains†

DOI10.1002/rsa.20968OpenAlexW2978357143MaRDI QIDQ6073630

No author found.

Publication date: 11 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20968

zbMATH Keywords

Markov chainsPotts modelapproximate countinghard-core modelexpander graphs

Mathematics Subject Classification ID

Computer science (68-XX) Statistical mechanics, structure of matter (82-XX)

Related Items

An FPTAS for the hardcore model on random regular bipartite graphs ⋮ Zeros and approximations of holant polynomials on the complex plane ⋮ Fast mixing via polymers for random graphs with unbounded degree ⋮ Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures ⋮ Approximately counting independent sets in bipartite graphs via graph containers ⋮ Sampling from the low temperature Potts model through a Markov chain on flows ⋮ Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022 ⋮ Low-temperature Ising dynamics with random initializations

Cites Work

• Unnamed Item
• Unnamed Item
• Interfaces in the Potts model. I: Pirogov-Sinai theory of the Fortuin- Kasteleyn representation
• Markov chain comparison
• On the hardness of sampling independent sets beyond the tree threshold
• Cluster expansion for abstract polymer models
• A unified approach to phase diagrams in field theory and statistical mechanics
• Comparison theorems for reversible Markov chains
• Comparison techniques for random walk on finite groups
• Loss network representation of Peierls contours
• Approximation algorithms for the normalizing constant of Gibbs distributions
• Analyzing Glauber dynamics by comparison of Markov chains
• Counting independent sets up to the tree threshold
• FPTAS for #BIS with Degree Bounds on One Side
• Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Mixing of the Glauber dynamics for the ferromagnetic Potts model
• Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Left and right convergence of graphs with bounded degree
• On Markov Chains for Independent Sets
• Algorithmic Pirogov-Sinai theory
• Algorithms for #BIS-hard problems on expander graphs
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs