Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

DOI10.1137/16M1101003zbMATH Open1383.68099MaRDI QIDQ4602373FDOQ4602373

Authors: Viresh Patel, Guus Regts 

Publication date: 10 January 2018

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

Recommendations

• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Zero-free regions of partition functions with applications to algorithms and graph limits
• scientific article; zbMATH DE number 7701429
• Inapproximability of the Tutte polynomial of a planar graph
• Inapproximability of the Tutte polynomial

zbMATH Keywords

approximation algorithmsgraph homomorphismpartition functionindependence polynomialTutte polynomialHolant problem

Mathematics Subject Classification ID

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

Cites Work

• The complexity of partition functions
• A complete dichotomy rises from the capture of vanishing signatures (extended abstract)
• Graph homomorphisms with complex values: a dichotomy theorem
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Counting independent sets up to the tree threshold
• Polynomial-Time Approximation Algorithms for the Ising Model
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
• Improved bounds for sampling colorings
• Computing the permanent of (some) complex matrices
• Computing the partition function for cliques in a graph
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Computing the partition function for graph homomorphisms
• The roots of the independence polynomial of a clawfree graph
• Computational complexity of Holant problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Left and right convergence of graphs with bounded degree
• Benjamini-Schramm continuity of root moments of graph polynomials
• Edge coloring models and reflection positivity
• Graph invariants related to statistical mechanical models: Examples and problems
• Edge coloring models as singular vertex coloring models
• Complex zero-free regions at large \(|q|\) for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• Tensor invariants for certain subgroups of the orthogonal group
• From Holant to \#CSP and back: dichotomy for Holant\(^{c }\) problems
• On a problem of Spencer
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• On Markov Chains for Independent Sets
• Zeros of chromatic and flow polynomials of graphs
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Ferromagnetic Potts model: refined \#BIS-hardness and related results
• Combinatorics and complexity of partition functions
• Computing the partition function for graph homomorphisms with multiplicities
• A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models
• A simple FPTAS for counting edge covers
• Zero-free regions of partition functions with applications to algorithms and graph limits
• On a conjecture of Sokal concerning roots of the independence polynomial
• Improved FPTAS for multi-spin systems
• Approximating permanents and hafnians
• On Approximately Counting Colorings of Small Degree Graphs
• Title not available (Why is that?)
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• On the number of \(B\)-flows of a graph
• The complexity of computing the sign of the Tutte polynomial (and consequent \#P-hardness of approximation)

Cited In (62)

• On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
• Lee-Yang zeros of the antiferromagnetic Ising model
• Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
• A spectral independence view on hard spheres via block dynamics
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Ising partition function: zeros and deterministic approximation
• Title not available (Why is that?)
• Zeros and approximations of holant polynomials on the complex plane
• 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
• Large scale stochastic dynamics. Abstracts from the workshop held September 15--21, 2019
• Some applications of Wagner's weighted subgraph counting polynomial
• The complexity of approximating the complex-valued Potts model
• The complexity of approximating the matching polynomial in the complex plane
• Absence of zeros implies strong spatial mixing
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Cayley trees do not determine the maximal zero-free locus of the independence polynomial
• More on zeros and approximation of the Ising partition function
• Title not available (Why is that?)
• Smoothed counting of 0–1 points in polyhedra
• Fast algorithms at low temperatures via Markov chains†
• On a conjecture of Sokal concerning roots of the independence polynomial
• Testing for dense subsets in a graph via the partition function
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Zero-freeness and approximation of real Boolean Holant problems
• Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• The complexity of approximating the complex-valued Potts model
• Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree
• Computing permanents of complex diagonally dominant matrices and tensors
• Fast mixing via polymers for random graphs with unbounded degree
• Title not available (Why is that?)
• The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Approximating real-rooted and stable polynomials, with combinatorial applications
• Correlation decay and the absence of zeros property of partition functions
• A Note on Deterministic Poly-Time Algorithms for Partition Functions Associated with Boolean Matrices with Prescribed Row and Column Sums
• New graph polynomials from the Bethe approximation of the Ising partition function
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
• Stability and complexity of mixed discriminants
• Weighted counting of solutions to sparse systems of equations
• Inapproximability of the independent set polynomial in the complex plane
• Algorithmic Pirogov-Sinai theory
• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• Counting independent sets in graphs with bounded bipartite pathwidth
• Algorithms for \#BIS-hard problems on expander graphs
• Fisher zeros and correlation decay in the Ising model
• Efficient algorithms for approximating quantum partition functions
• Fisher Zeros and Correlation Decay in the Ising Model
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• Spectral independence via stability and applications to Holant-type problems
• A near-optimal zero-free disk for the Ising model
• Improved bounds for the zeros of the chromatic polynomial via Whitney's broken circuit theorem
• On the zeroes of hypergraph independence polynomials
• Quasipolynomial-time algorithms for Gibbs point processes
• Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
• Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite \(\Delta \)-regular tree for large \(\Delta \)
• The complexity of ferromagnetic 2-spin systems on bounded degree graphs
• Algorithms for hard-constraint point processes via discretization
• Approximating the chromatic polynomial is as hard as computing it exactly

This page was built for publication: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

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