#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region by Goldberg, L, Galanis, A, Cai, J, Guo, H, Jerrum, M, Stefankovic, D, Vigoda, E

“…Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. …”

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results by Galanis, A, Štefankovič, D, Vigoda, E, Yang, L

“…Goldberg and Jerrum showed that approximating the partition function of the ferromagnetic Potts model is at least as hard as approximating the number of independent sets in bipartite graphs, so-called #BIS-hardness. We improve this hardness result by establishing it for bipartite graphs of maximum degree $\Delta$. …”

Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region by Galanis, A, Stefankovic, D, Vigoda, E

“…<br/> The main difficulty in previous inapproximability results was analyzing the behavior of the model on random Δ-regular bipartite graphs, which served as the gadget in the reduction. …”

Inapproximability of the partition function for the antiferromagnetic ising and hard-core models by Galanis, A, Stefankovic, D, Vigoda, E

“…Our proof works by relating certain second moment calculations for random Δ-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree. …”