4 papers
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…
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…
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…