Improved FPTAS for multi-spin systems

DOI10.1007/978-3-642-40328-6_44MaRDI QIDQ2851891zbMATH OpenOpenAlexFDO

Authors Pinyan Lu, Yitong Yin

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40328-6_44

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Approximation algorithms (68W25) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Recommendations

• Approximate counting via correlation decay in spin systems
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Correlation decay and deterministic FPTAS for counting list-colorings of a graph
• An FPTAS for counting proper four-colorings on cubic graphs
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

Cited in

(20)

• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Counting hypergraph matchings up to uniqueness threshold
• Zero-free regions of partition functions with applications to algorithms and graph limits
• An FPTAS for the hardcore model on random regular bipartite graphs
• What can be sampled locally?
• On a conjecture of Sokal concerning roots of the independence polynomial
• Correlation decay and deterministic FPTAS for counting list-colorings of a graph
• An FPTAS for counting proper four-colorings on cubic graphs
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Improved bounds for perfect sampling of \(k\)-colorings in graphs
• FPTAS for weighted Fibonacci gates and its applications
• Counting hypergraph colorings in the local lemma regime
• Approximate counting via correlation decay in spin systems
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Absence of zeros implies strong spatial mixing
• Correlation decay and the absence of zeros property of partition functions
• Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite -regular tree for large
• Deterministic approximate counting of colorings with fewer than 2 colors via absence of zeros
• Correlation decay and partition function zeros: algorithms and phase transitions
• On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs

This page was built for publication: Improved FPTAS for multi-spin systems

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