27 citations · 58 across the 5 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2017★ 20 cited
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…
cs.CC2015
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…