Guus Regts

activity

20102026

most citedDeterministic polynomial-time approximation algorithms for partition functions and graph polynomials

115 citations · 254 across the 43 of their papers we have counts for

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2022

Approximating the chromatic polynomial is as hard as computing it exactly

Ferenc Bencs, Jeroen Huijben, Guus Regts

We show that for any non-real algebraic number $q$ such that $∣ q - 1∣ > 1$ or $ℜ (q) > \frac{3}{2}$ it is \textsc{\#P}-hard to compute a multiplicative (resp. additive) approximation to…

cs.CC2020

Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

Pjotr Buys, Andreas Galanis, Viresh Patel +1

We study the computational complexity of approximating the partition function of the ferromagnetic Ising model with the external field parameter $λ$ on the unit circle in the compl…