33 citations · 52 across the 13 of their papers we have counts for
13 papers
The framework to unify all complexity dichotomy theorems for Boolean tensor networks
Mingji Xia
Fixing an arbitrary set of complex-valued functions over Boolean variables yields a counting problem . Taking only functions from to form…
Parameterizing the Permanent: Hardness for -minor-free graphs
Radu Curticapean, Mingji Xia
In the 1960s, statistical physicists discovered a fascinating algorithm for counting perfect matchings in planar graphs. Valiant later showed that the same problem is #P-hard for g…
Rectangle Transformation Problem
Shaojiang Wang, Kun He, Yicheng Pan +1
In this paper, we propose the rectangle transformation problem (RTP) and its variants. RTP asks for a transformation by a rectangle partition between two rectangles of the same are…
Variable Version Lovász Local Lemma: Beyond Shearer's Bound
Kun He, Liang Li, Xingwu Liu +2
A tight criterion under which the abstract version Lovász Local Lemma (abstract-LLL) holds was given by Shearer decades ago. However, little is known about that of the variable ver…
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…