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

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) 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

(18)

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

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)