5 papers
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…
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 i…
How Hard is it to be a Star? Convex Geometry and the Real Hierarchy
Marcus Schaefer, Daniel Å tefankoviÄ
A set is star-shaped if there is a point in the set that can see every other point in the set in the sense that the line-segment connecting the points lies within the set. We show…
Spectral Independence and Local-to-Global Techniques for Optimal Mixing of Markov Chains
Zongchen Chen, Daniel Stefankovic, Eric Vigoda
This monograph is an exposition on an exciting new technique known as spectral independence, which has been instrumental in analyzing the convergence rate of Markov Chain Monte Car…
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…