1 citations · 1 across the 11 of their papers we have counts for
18 papers
Approximating Combinatorial Contracts with Arbitrary Costs
Xiaotie Deng, Hanyu Li, Chenghua Liu
We study single-agent combinatorial contracts under linear payments. Under a reward share , an agent chooses a subset of hidden actions, generating reward …
Cardinality-Constrained Randomized Assortments with Balanced Market Share
Xiaotie Deng, Hanyu Li, Chenghua Liu
Assortment optimization asks a seller which of products to display to each customer. Under the multinomial-logit (MNL) model, a revenue-maximizing policy may concentrate most p…
Exact Hill Shares Are Simultaneous Guarantees
Bo Li, Hanyu Li, Chenghua Liu
Fair division of indivisible bads seeks allocations that guarantee every agent a bundle whose cost is no larger than a meaningful fairness benchmark. The canonical minimax share ha…
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…
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…
Quantum Speedups for Log-Concave Sampling from Local Structure
Chenghua Liu, Qisheng Wang, Zhengfeng Ji
For a convex function , the problem of sampling from a distribution proportional to is called log-concave sampling. In many practi…
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…
Rank-Independent Spectral Hypergraph Sparsification via Global-Dictionary Chaining
Chenghua Liu, Yuxin Zhang
We show that every weighted hypergraph on vertices admits a spectral -sparsifier with hyperedges, strengthening the independent STOC 202…
Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
Minbo Gao, Chenghua Liu, Guangxu Yang +1
We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to…
Lévy-Khintchine Structure Enables Fast-Forwardable Lindbladian Simulation
Minbo Gao, Zhengfeng Ji, Chenghua Liu
Simulation of open quantum systems is an area of active research in quantum algorithms. In this work, we revisit the connection between Markovian open-system dynamics and averages…
Accelerating Regression Tasks with Quantum Algorithms
Chenghua Liu, Zhengfeng Ji
Regression is a cornerstone of statistics and machine learning, with applications spanning science, engineering, and economics. While quantum algorithms for regression have attract…
Quantum Speedup for Hypergraph Sparsification
Chenghua Liu, Minbo Gao, Zhengfeng Ji +1
Graph sparsification serves as a foundation for many algorithms, such as approximation algorithms for graph cuts and Laplacian system solvers. As its natural generalization, hyperg…
Quantum Speedup for Sampling Random Spanning Trees
Simon Apers, Minbo Gao, Zhengfeng Ji +1
We present a quantum algorithm for sampling random spanning trees from a weighted graph in time, where and denote the number of vertices and edge…