124 citations · 239 across the 28 of their papers we have counts for
3 papers · 1 filter
Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
Andreas Galanis, Daniel Stefankovic, Eric Vigoda +1
Recent results establish for 2-spin antiferromagnetic systems that the computational complexity of approximating the partition function on graphs of maximum degree D undergoes a ph…
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg +4
Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an…
Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximat…