27 citations · 58 across the 5 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…
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables
Ivona Bezakova, Alistair Sinclair, Daniel Stefankovic +1
The sequential importance sampling (SIS) algorithm has gained considerable popularity for its empirical success. One of its noted applications is to the binary contingency tables p…