1 citations · 1 across the 2 of their papers we have counts for
5 papers
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…
FlashPrefill: Instantaneous Pattern Discovery and Thresholding for Ultra-Fast Long-Context Prefilling
Qihang Fan, Huaibo Huang, Zhiying Wu +3
Long-context modeling is a pivotal capability for Large Language Models, yet the quadratic complexity of attention remains a critical bottleneck, particularly during the compute-in…
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…