Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
Chenghua Liu, Boning Meng
In a landmark JACM paper recognized with the 2021 G{ö}del Prize, Cai and Chen established a complete complexity dichotomy for counting CSPs over arbitrary finite domains with algeb…
cs.CC2026
The Counting General Dominating Set Framework
Jiayi Zheng, Boning Meng
We introduce a new framework of counting problems called #GDS that encompasses #-Set, a class of domination-type problems that includes counting dominating sets and count…
cs.CC2025
Dichotomies for \#CSP on graphs that forbid a clique as a minor
Boning Meng, Yicheng Pan
We prove complexity dichotomies for \#CSP problems (not necessarily symmetric) with Boolean domain and complex range on several typical minor-closed graph classes. These dichotomie…