124 citations · 275 across the 42 of their papers we have counts for
13 papers · 1 filter
Critical window for approximate counting in dense Ising models
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
We study the complexity of approximating the partition function of dense Ising models in the critical regime. Recent work of Chen, Chen, Yin, and Zhang (FOCS 2025) established fast…
Beyond the Existential Theory of the Reals
Marcus Schaefer, Daniel Stefankovic
We show that completeness at higher levels of the theory of the reals is a robust notion (under changing the signature and bounding the domain of the quantifiers). This mends recog…
Approximating observables is as hard as counting
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
We study the computational complexity of estimating local observables for Gibbs distributions. A simple combinatorial example is the average size of an independent set in a graph.…
The complexity of approximating averages on bounded-degree graphs
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
We prove that, unless P=NP, there is no polynomial-time algorithm to approximate within some multiplicative constant the average size of an independent set in graphs of maximum deg…
Inapproximability of the independent set polynomial in the complex plane
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg +1
We study the complexity of approximating the independent set polynomial of a graph with maximum degree when the activity is a complex number. This problem is a…
Implementations and the independent set polynomial below the Shearer threshold
Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
The independent set polynomial is important in many areas. For every integer , the Shearer threshold is the value . It is known that for $λ< - λ^*…