activity
19992023
most cited#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region

37 citations · 213 across the 42 of their papers we have counts for

collaborators
Showing 2016Show all

1 paper · 1 filter

cs.CC2016★ 2 cited

Holographic Algorithm with Matchgates Is Universal for Planar CSP Over Boolean Domain

Jin-yi Cai, Zhiguo Fu

We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (CSP) over Boolean variables into exactly three categories: (1) Polyn…