37 citations · 171 across the 30 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.CC2013★ 37 cited
#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…
cs.DS2013
Holographic Algorithms Beyond Matchgates
Jin-Yi Cai, Heng Guo, Tyson Williams
Holographic algorithms introduced by Valiant are composed of two ingredients: matchgates, which are gadgets realizing local constraint functions by weighted planar perfect matching…