11 citations · 29 across the 12 of their papers we have counts for
13 papers
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…
Beyond Windability: An FPRAS for The Six-Vertex Model
Zhiguo Fu, Junda Li, Xiongxin Yang
The six-vertex model is an important model in statistical physics and has deep connections with counting problems. There have been some fully polynomial randomized approximation sc…
The Implicit Regularization of Momentum Gradient Descent with Early Stopping
Li Wang, Yingcong Zhou, Zhiguo Fu
The study on the implicit regularization induced by gradient-based optimization is a longstanding pursuit. In the present paper, we characterize the implicit regularization of mome…
From Holant to Quantum Entanglement and Back
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
Holant problems are intimately connected with quantum theory as tensor networks. We first use techniques from Holant theory to derive new and improved results for quantum entanglem…
Beyond #CSP: A Dichotomy for Counting Weighted Eulerian Orientations with ARS
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
We define and explore a notion of unique prime factorization for constraint functions, and use this as a new tool to prove a complexity classification for counting weighted Euleria…
On Blockwise Symmetric Matchgate Signatures and Higher Domain \#CSP
Zhiguo Fu
For any and , we prove that the {\sc Equality} function on variables over a domain of size cannot be realized by matchgates under holographic tr…
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…
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…
A Holant Dichotomy: Is the FKT Algorithm Universal?
Jin-Yi Cai, Zhiguo Fu, Heng Guo +1
We prove a complexity dichotomy for complex-weighted Holant problems with an arbitrary set of symmetric constraint functions on Boolean variables. This dichotomy is specifically to…
A Collapse Theorem for Holographic Algorithms with Matchgates on Domain Size at Most 4
Jin-Yi Cai, Zhiguo Fu
Holographic algorithms with matchgates are a novel approach to design polynomial time computation. It uses Kasteleyn's algorithm for perfect matchings, and more importantly a holog…
Holographaic Alogorithms on Bases of Rank 2
Zhiguo Fu, Fengqin Yang
An essential problem in the design of holographic algorithms is to decide whether the required signatures can be realized by matchgates under a suitable basis transformation (SRP).…