27 citations · 53 across the 4 of their papers we have counts for
7 papers
Fast sampling via spectral independence beyond bounded-degree graphs
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg +1
Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal…
Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
Ivona Bezakova, Antonio Blanca, Zongchen Chen +2
We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the mod…
The complexity of approximating the matching polynomial in the complex plane
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg +1
We study the problem of approximating the value of the matching polynomial on graphs with edge parameter , where takes arbitrary values in the complex plane. When is a p…
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…
Finding Detours is Fixed-parameter Tractable
Ivona Bezáková, Radu Curticapean, Holger Dell +1
We consider the following natural "above guarantee" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G, and an integer k, the problem L…
Approximation via Correlation Decay when Strong Spatial Mixing Fails
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg +2
Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of…