1 citations · 1 across the 2 of their papers we have counts for
4 papers · 1 filter
A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems
Chenghua Liu, Boning Meng, Juqiu Wang
We prove a complexity dichotomy for Boolean Holant problems defined by arbitrary finite sets of algebraic complex-valued signatures. The tractable cases are characterized by an exp…
The versus #P dichotomy for #EO
Boning Meng, Juqiu Wang, Mingji Xia
The complexity classification of the Holant problem has remained unresolved for the past fifteen years. Counting complex-weighted Eulerian orientation problems, denoted as #EO, is…
From an odd arity signature to a Holant dichotomy
Boning Meng, Juqiu Wang, Mingji Xia +1
\textsf{Holant} is an essential framework in the field of counting complexity. For over fifteen years, researchers have been clarifying the complexity classification for complex-va…
P-time Algorithms for Typical #EO Problems
Boning Meng, Juqiu Wang, Mingji Xia
In this article, we study the computational complexity of counting weighted Eulerian orientations, denoted as \#\textsf{EO}. This problem is considered a pivotal scenario in the co…