A complexity trichotomy for approximately counting list H-colourings by Goldberg, L, Galanis, A, Jerrum, M

“…If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. …”

A complexity trichotomy for approximately counting list H-colourings by Galanis, A, Goldberg, L, Jerrum, M

“…If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. …”

Approximately counting H-colourings is BIS-Hard by Galanis, A, Goldberg, L, Jerrum, M

“…We show that for any fixed graph <em>H</em> without trivial components, this is as hard as the well-known problem #BIS, the problem of (approximately) counting independent sets in a bipartite graph. #BIS is a complete problem in an important complexity class for approximate counting, and is believed not to have an FPRAS. …”

Approximately counting H-colourings is #BIS-hard by Galanis, A, Goldberg, L, Jerrum, M

“…We show that if H is any fixed graph without trivial components, then the problem is as hard as the well-known problem #BIS, which is the problem of (approximately) counting independent sets in a bipartite graph. #BIS is a complete problem in a important complexity class for approximate counting, and is believed not to have an FPRAS. …”

#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. …”

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems by Galanis, A, Goldberg, L, Yang, K

“…Our main result shows that: (i) if every function in &Gamma; is affine, then #CSP∆(&Gamma;) is in FP for all ∆, (ii) otherwise, if every function in &Gamma; is in a class called IM2, then for large ∆, #CSP∆(&Gamma;) is equivalent under approximation-preserving reductions to the problem of counting independent sets in bipartite graphs, (iii) otherwise, for large ∆, it is NP-hard to approximate #CSP∆(&Gamma;), even within an exponential factor.…”

Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems by Galanis, A, Goldberg, L, Yang, K

“…Our main result shows that: (i) if every function in Γ is affine, then #CSPΔ(Γ) is in FP for all Δ, (ii) otherwise, if every function in Γ is in a class called IM2, then for all sufficiently large Δ, #CSPΔ(Γ) is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large Δ, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSPΔ(Γ), even within an exponential factor. …”

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. …”

Inapproximability of counting hypergraph colourings by Galanis, A, Guo, H, Wang, J

“…This allows us to utilise reduction techniques available for the graph case, which hinge upon understanding the behaviour on random regular bipartite graphs that serve as gadgets in the reduction. …”