10 papers · 1 filter
A Dichotomy for Planar Graph Homomorphisms with Nonnegative Weights
Chenghua Liu, Boning Meng
We prove a complete complexity dichotomy for planar graph homomorphism counting with any fixed symmetric nonnegative matrix of arbitrary finite order, giving an explicit criterion…
Hidden Circuits and Exact Counting in Ordered Graphs
Chenghua Liu, Boning Meng
We prove that counting perfect matchings is -complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit inte…
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…
When Matchgate Base Collapse Fails: A Qutrit Trichotomy and Unbounded Exact Width
Chenghua Liu, Boning Meng
Holographic algorithms solve planar counting problems by encoding each value of a finite domain into several Boolean matchgate wires. Base collapse asks whether every exact represe…
Bounded Relative Boundary Implies Narrow DNF Approximation
Chenghua Liu, Boning Meng
Friedgut conjectured that an increasing family in the -biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements hav…
A Dichotomy for Complex Boolean Holant with Binary Disequality
Chenghua Liu, Boning Meng
We prove a complexity dichotomy for Boolean Holant problems defined by arbitrary finite sets of algebraic complex-valued signatures when binary disequality is available. The tracta…
Lower Bounds for Domination-Type Problems Parameterized by Rank-Width
Chenghua Liu, Boning Meng
For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite \((σ,ρ)\)-problems and of Bergougnoux…
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…
The Counting General Dominating Set Framework
Jiayi Zheng, Boning Meng
We introduce a new framework of counting problems called #GDS that generalizes #-Set, a class of domination-type problems that includes counting dominating sets and countin…
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…