Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results

DOI10.1137/140997580zbMath1355.68198OpenAlexW2962998907MaRDI QIDQ5506693

Daniel Štefanković, Eric Vigoda, Linji Yang, Andreas Galanis

Publication date: 13 December 2016

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4731/

zbMATH Keywords

phase transitionsrandom regular graphsspin systemsapproximate countingferromagnetic Potts model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (25)

An FPTAS for the hardcore model on random regular bipartite graphs ⋮ Evaluations of Tutte polynomials of regular graphs ⋮ Algorithmic Pirogov-Sinai theory ⋮ 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 ⋮ Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs ⋮ Metastability of the Potts ferromagnet on random regular graphs ⋮ Approximation Algorithms for the Random Field Ising Model ⋮ Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics ⋮ Unnamed Item ⋮ Random cluster model on regular graphs ⋮ On the uniqueness of Gibbs measure in the Potts model on a Cayley tree with external field ⋮ Swendsen‐Wang algorithm on the mean‐field Potts model ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Faster exponential-time algorithms for approximately counting independent sets ⋮ A fixed-parameter perspective on \#BIS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Random-cluster dynamics on random regular graphs in tree uniqueness ⋮ Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs ⋮ Unnamed Item ⋮ Gibbs measures of Potts model on Cayley trees: A survey and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Gibbs measures and phase transitions.
• Ising models on locally tree-like graphs
• On the hardness of sampling independent sets beyond the tree threshold
• On the chromatic number of random \(d\)-regular graphs
• Loss networks
• Schur multipliers
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• The Glauber dynamics of colorings on trees is rapidly mixing throughout the nonreconstruction regime
• Glauber dynamics on trees: Boundary conditions and mixing time
• The relative complexity of approximate counting problems
• The random-cluster model on a homogeneous tree
• Exact thresholds for Ising-Gibbs samplers on general graphs
• The Swendsen-Wang process does not always mix rapidly
• The number of solutions for random regular NAE-SAT
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• Factor models on locally tree-like graphs
• The replica symmetric solution for Potts models on \(d\)-regular graphs
• Improved inapproximability results for counting independent sets in the hard-core model
• Counting independent sets up to the tree threshold
• The complexity of approximating conservative counting CSPs.
• The Complexity of Ferromagnetic Two-spin Systems with External Fields
• Polynomial-Time Approximation Algorithms for the Ising Model
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Complete analysis of phase transitions and ensemble equivalence for the Curie–Weiss–Potts model
• Approximating the Partition Function of the Ferromagnetic Potts Model
• Mathematical Aspects of Mixing Times in Markov Chains
• Information, Physics, and Computation
• The Complexity of Enumeration and Reliability Problems
• Almost all regular graphs are hamiltonian
• The computational complexity of two‐state spin systems
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• The expressibility of functions on the boolean domain, with applications to counting CSPs
• Fast mixing for independent sets, colorings, and other models on trees
• The Random-Cluster Model
• Rapid mixing of Swendsen–Wang dynamics in two dimensions
• Correlation Decay up to Uniqueness in Spin Systems
• The condensation phase transition in random graph coloring

This page was built for publication: Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results