1 citations · 1 across the 11 of their papers we have counts for
12 papers
Optimal Covariance Inflation under Gaussian Tilts
Minbo Gao, Zhengfeng Ji, Chenghua Liu
Covariance-sensitive analyses of Gaussian annealing for sampling from a convex body require controlling how much covariance can grow under a radial Gaussian tilt. For an isotropic…
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…
A Correlation-Gap Bound for Nonlinear Gaussian PCA
Minbo Gao, Zhengfeng Ji, Chenghua Liu
Principal component analysis (PCA) is optimal for the linear reconstruction of Gaussian data, a foundational property underlying its central role in algorithms and signal processin…