33 citations · 52 across the 13 of their papers we have counts for
10 papers · 1 filter
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…
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…
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation mod 2^k
Radu Curticapean, Mingji Xia
We identify and study relevant structural parameters for the problem PerfMatch of counting perfect matchings in a given input graph . These generalize the well-known tractable p…
Base collapse of holographic algorithms
Mingji Xia
A holographic algorithm solves a problem in domain of size , by reducing it to counting perfect matchings in planar graphs. It may simulate a -value variable by a bunch of $t…