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