Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials

DOI10.1137/16M1101003zbMath1383.68099MaRDI QIDQ4602373

Viresh Patel, Guus Regts

Publication date: 10 January 2018

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

zbMATH Keywords

partition functiongraph homomorphismTutte polynomialapproximation algorithmsindependence polynomialHolant problem

Mathematics Subject Classification ID

Graph polynomials (05C31) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs, Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree, The complexity of approximating the complex-valued Potts model, Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction, Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs, Approximating real-rooted and stable polynomials, with combinatorial applications, A Spectral Independence View on Hard Spheres via Block Dynamics, Zero-freeness and approximation of real Boolean Holant problems, Lee-Yang zeros of the antiferromagnetic Ising model, Zeros and approximations of holant polynomials on the complex plane, Algorithmic Pirogov-Sinai theory, Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing, Fast mixing via polymers for random graphs with unbounded degree, Absence of zeros implies strong spatial mixing, Smoothed counting of 0–1 points in polyhedra, Combinatorics. Abstracts from the workshop held January 1--7, 2023, Fast algorithms at low temperatures via Markov chains†, 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 \(\Delta \)-regular tree for large \(\Delta \), Algorithms for hard-constraint point processes via discretization, Approximating the chromatic polynomial is as hard as computing it exactly, Unnamed Item, Unnamed Item, Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial, Large scale stochastic dynamics. Abstracts from the workshop held September 15--21, 2019, Inapproximability of the Independent Set Polynomial in the Complex Plane, The Ising partition function: zeros and deterministic approximation, Location of zeros for the partition function of the Ising model on bounded degree graphs, Algorithms for #BIS-Hard Problems on Expander Graphs, Some applications of Wagner's weighted subgraph counting polynomial, Computing the number of induced copies of a fixed graph in a bounded degree graph, Cayley trees do not determine the maximal zero-free locus of the independence polynomial, Counting independent sets in graphs with bounded bipartite pathwidth, Unnamed Item, Unnamed Item, Unnamed Item, On a conjecture of Sokal concerning roots of the independence polynomial, Fisher zeros and correlation decay in the Ising model, Stability and complexity of mixed discriminants, Testing for Dense Subsets in a Graph via the Partition Function, Weighted counting of solutions to sparse systems of equations, Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems, Fisher Zeros and Correlation Decay in the Ising Model, Computing permanents of complex diagonally dominant matrices and tensors, More on zeros and approximation of the Ising partition function, The complexity of approximating the complex-valued Potts model, Efficient algorithms for approximating quantum partition functions, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs, Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the permanent of (some) complex matrices
• Tensor invariants for certain subgroups of the orthogonal group
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Combinatorics and complexity of partition functions
• Computing the partition function for graph homomorphisms
• Graph invariants related to statistical mechanical models: Examples and problems
• The roots of the independence polynomial of a clawfree graph
• Computing the partition function for graph homomorphisms with multiplicities
• Benjamini-Schramm continuity of root moments of graph polynomials
• On a problem of Spencer
• Zeros of chromatic and flow polynomials of graphs
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• Zero-free regions of partition functions with applications to algorithms and graph limits
• Complex zero-free regions at large \(|q|\) for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• On a conjecture of Sokal concerning roots of the independence polynomial
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• On the number of \(B\)-flows of a graph
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• The complexity of partition functions
• A Personal List of Unsolved Problems Concerning Lattice Gases and Antiferromagnetic Potts Models
• Improved bounds for sampling colorings
• The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation)
• Improved FPTAS for Multi-spin Systems
• Counting independent sets up to the tree threshold
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• From Holant to #CSP and Back: Dichotomy for Holant c Problems
• Computational Complexity of Holant Problems
• Polynomial-Time Approximation Algorithms for the Ising Model
• Computing the partition function for cliques in a graph
• Approximating the Partition Function of the Ferromagnetic Potts Model
• Edge coloring models and reflection positivity
• On Approximately Counting Colorings of Small Degree Graphs
• Approximating permanents and hafnians
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Left and right convergence of graphs with bounded degree
• On Markov Chains for Independent Sets
• A Simple FPTAS for Counting Edge Covers
• A complete dichotomy rises from the capture of vanishing signatures
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem