Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial

DOI10.1017/s030500412300052xarXiv2104.11615OpenAlexW3158421144MaRDI QIDQ6198132

Pjotr Buys, Unnamed Author, Lorenzo Guerini, Guus Regts, Han Peters

Publication date: 20 February 2024

Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2104.11615

zbMATH Keywords

phase transitionscomputational hardnesscomplex zeros of polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of roots of polynomial equations (65H04)

Cites Work

• Unnamed Item
• Unnamed Item
• Counting in two-spin models on \(d\)-regular graphs
• Combinatorics and complexity of partition functions
• The complexity of computing the permanent
• On a problem of Spencer
• The Hausdorff dimension of the boundary of the Mandelbrot set and Julia sets
• Complex dynamics
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• On trees with real-rooted independence polynomial
• Cayley trees do not determine the maximal zero-free locus of the independence polynomial
• 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
• Theory of monomer-dimer systems
• On the hardness of approximate reasoning
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Counting independent sets up to the tree threshold
• On the dynamics of rational maps
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• Inapproximability of the Independent Set Polynomial in the Complex Plane
• Computational Complexity
• Dynamics in One Complex Variable. (AM-160)
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation

This page was built for publication: Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial