14 papers
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…
Independent Set Discovery on Biclique-Free Graphs Is Fixed-Parameter Tractable
Chenghua Liu, Boning Meng
\textnormal{\textsc{Independent Set Discovery}} asks whether a configuration of tokens on distinct vertices can be transformed into an independent -set by a sequence of toke…
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…
Quantum Uncomputation of Clean and Dirty Ancilla Qubits
Chenke Liu, Li Zhou, Boning Meng
Automatic uncomputation aims to provide programming-language-level support to facilitate the correct and safe use of ancilla qubits in quantum computing, but efforts have only been…
Bona: Automatic Management of Dirty Ancilla Borrowing in Quantum Circuits
Xiaoquan Xu, Chenke Liu, Boning Meng +2
The management of ancilla qubits has become a critical technique for reducing quantum circuit width. Dirty ancillas, which may be borrowed from any temporarily idle qubit regardles…
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…
Matchgate signatures under variable permutations
Boning Meng, Yicheng Pan
In this article, we give a sufficient and necessary condition for determining whether a matchgate signature retains its property under a certain variable permutation, which can be…