Improved FPTAS for multi-spin systems
DOI10.1007/978-3-642-40328-6_44zbMATH Open1405.68446OpenAlexW9125994MaRDI QIDQ2851891FDOQ2851891
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
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
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)
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)
