Showing cs.CCShow all
3 papers · 1 filter
cs.CC2024
A combinatorial view of Holant problems on higher domains
Yin Liu
On the Boolean domain, there is a class of symmetric signatures called ``Fibonacci gates'' for which a beautiful P-time combinatorial algorithm has been designed for the correspond…
cs.CC2023
Restricted Holant Dichotomy on Domains 3 and 4
Yin Liu, Austen Z. Fan, Jin-Yi Cai
denotes a class of counting problems specified by a constraint function . We prove complexity dichotomy theorems for in…
cs.CC2021
Bipartite 3-Regular Counting Problems with Mixed Signs
Jin-Yi Cai, Austen Z. Fan, Yin Liu
We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. For every problem of the form $\operatorname{Holant}\left(f\mid…