Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
From MaRDI portal
Publication:4602373
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
Cites work
- scientific article; zbMATH DE number 5485444 (Why is no real title available?)
- scientific article; zbMATH DE number 1545676 (Why is no real title available?)
- scientific article; zbMATH DE number 7204480 (Why is no real title available?)
- A complete dichotomy rises from the capture of vanishing signatures (extended abstract)
- A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models
- A simple FPTAS for counting edge covers
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Approximating permanents and hafnians
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Benjamini-Schramm continuity of root moments of graph polynomials
- Combinatorics and complexity of partition functions
- Complex zero-free regions at large \(|q|\) for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
- Computational complexity of Holant problems
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- Computing the partition function for cliques in a graph
- Computing the partition function for graph homomorphisms
- Computing the partition function for graph homomorphisms with multiplicities
- Computing the permanent of (some) complex matrices
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Counting independent sets up to the tree threshold
- Edge coloring models and reflection positivity
- Edge coloring models as singular vertex coloring models
- Ferromagnetic Potts model: refined \#BIS-hardness and related results
- From Holant to \#CSP and back: dichotomy for Holant\(^{c }\) problems
- Graph homomorphisms with complex values: a dichotomy theorem
- Graph invariants related to statistical mechanical models: Examples and problems
- Improved FPTAS for multi-spin systems
- Improved bounds for sampling colorings
- Left and right convergence of graphs with bounded degree
- On Approximately Counting Colorings of Small Degree Graphs
- On Markov Chains for Independent Sets
- On a conjecture of Sokal concerning roots of the independence polynomial
- On a problem of Spencer
- On the number of \(B\)-flows of a graph
- Polynomial-Time Approximation Algorithms for the Ising Model
- Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
- Tensor invariants for certain subgroups of the orthogonal group
- The complexity of computing the sign of the Tutte polynomial (and consequent \#P-hardness of approximation)
- The complexity of partition functions
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- The roots of the independence polynomial of a clawfree graph
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Zeros of chromatic and flow polynomials of graphs
Cited in
(62)- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- 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
- scientific article; zbMATH DE number 7561741 (Why is no real title available?)
- The Ising partition function: zeros and deterministic approximation
- scientific article; zbMATH DE number 7650115 (Why is no real title available?)
- Zeros and approximations of holant polynomials on the complex plane
- scientific article; zbMATH DE number 7559110 (Why is no real title available?)
- 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
- The complexity of approximating the complex-valued Potts model
- Some applications of Wagner's weighted subgraph counting polynomial
- The complexity of approximating the matching polynomial in the complex plane
- 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
- Spectral independence via stability and applications to Holant-type problems
- Absence of zeros implies strong spatial mixing
- More on zeros and approximation of the Ising partition function
- scientific article; zbMATH DE number 7701429 (Why is no real title available?)
- On a conjecture of Sokal concerning roots of the independence polynomial
- Smoothed counting of 0–1 points in polyhedra
- Fast algorithms at low temperatures via Markov chains†
- Testing for dense subsets in a graph via the partition function
- Zero-freeness and approximation of real Boolean Holant problems
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- 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
- 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
- On the zeroes of hypergraph independence polynomials
- Quasipolynomial-time algorithms for Gibbs point processes
- The complexity of approximating the complex-valued Potts model
- 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 \)
- 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
- scientific article; zbMATH DE number 7650108 (Why is no real title available?)
- 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
- Algorithmic Pirogov-Sinai theory
- Stability and complexity of mixed discriminants
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
- Weighted counting of solutions to sparse systems of equations
- Inapproximability of the independent set polynomial in the complex plane
- Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
- The complexity of ferromagnetic 2-spin systems 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
- Algorithms for hard-constraint point processes via discretization
- Approximating the chromatic polynomial is as hard as computing it exactly
- Fisher Zeros and Correlation Decay in the Ising Model
- Efficient algorithms for approximating quantum partition functions
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)
