37 citations · 213 across the 42 of their papers we have counts for
6 papers · 1 filter
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…
Clifford Gates in the Holant Framework
Jin-Yi Cai, Heng Guo, Tyson Williams
We show that the Clifford gates and stabilizer circuits in the quantum computing literature, which admit efficient classical simulation, are equivalent to affine signatures under a…
New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
We discover new P-time computable six-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. We further prove that there are no more: To…
Complexity Classification of the Eight-Vertex Model
Jin-Yi Cai, Zhiguo Fu
We prove a complexity dichotomy theorem for the eight-vertex model. For every setting of the parameters of the model, we prove that computing the partition function is either solva…
Complexity Classification Of The Six-Vertex Model
Jin-Yi Cai, Zhiguo Fu, Mingji Xia
We prove a complexity dichotomy theorem for the six-vertex model. For every setting of the parameters of the model, we prove that computing the partition function is either solvabl…
Dichotomy for Real Holant Problems
Jin-Yi Cai, Pinyan Lu, Mingji Xia
Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks, with count…