39 citations · 79 across the 15 of their papers we have counts for
5 papers · 1 filter
Approximability of the Four-Vertex Model
Zhiguo Fu, Tianyu Liu, Xiongxin Yang
We study the approximability of the four-vertex model, a special case of the six-vertex model.We prove that, despite being NP-hard to approximate in the worst case, the four-vertex…
FPRAS via MCMC where it mixes torpidly (and very little effort)
Jin-Yi Cai, Tianyu Liu
Is Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for a problem via an MCMC algorithm possible when it is known that rapid mixing provably fails? We introduce severa…
Counting perfect matchings and the eight-vertex model
Jin-Yi Cai, Tianyu Liu
We study the approximation complexity of the partition function of the eight-vertex model on general 4-regular graphs. For the first time, we relate the approximability of the eigh…
Approximability of the Eight-vertex Model
Jin-Yi Cai, Tianyu Liu, Pinyan Lu +1
We initiate a study of the classification of approximation complexity of the eight-vertex model defined over 4-regular graphs. The eight-vertex model, together with its special cas…
Approximability of the Six-vertex Model
Jin-Yi Cai, Tianyu Liu, Pinyan Lu
In this paper we take the first step toward a classification of the approximation complexity of the six-vertex model, an object of extensive research in statistical physics. Our co…