Learning a motion prior requires a reward that guides a policy from its current behavior toward demonstrated motion. Adversarial Motion Priors (AMP) provide such a reward with a discriminator. However, adversarial objectives can become uninformative when policy and expert supports are far apart. A naive use of optimal...
Yi-Lin Zou, Cheng-Hua Liu, Cheng-Long Wu et al.· 0 citations
Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle $U_A$ and the right-hand side through a state-preparation oracle $U_b$. The optimal query complexities of these two oracles are known separately: $O(\kappa\log(1/\varepsilon))$ queries to $U_A$ and $O(\kappa/s)$ queries to $U...
Minbo Gao, Zheng-Feng Ji, Cheng-Hua Liu· 0 citations
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 convex body $K\subseteq\mathbb{R}^n$, let $\mu_{K,t} (\mathrm{d} x) \propto e^{-t\| x \| ^2} \mathbb{1}_K(x)\,\mathrm{d} x$, and let $Q_n$ b...
Minbo Gao, Zheng-Feng Ji, Cheng-Hua Liu· 0 citations
We study single-agent combinatorial contracts under linear payments. Under a reward share $\alpha\in[0,1]$, an agent chooses a subset $S$ of $n$ hidden actions, generating reward $f(S)$ at cost $c(S)$, to maximize $\alpha f(S)-c(S)$, while the principal receives $(1-\alpha)f(S)$. For nonnegative additive rewards and mo...
For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite \((\sigma,\rho)\)-problems and of Bergougnoux and Kant\'e (\emph{SIAM J. Discrete Math.}, 2021) for Connected Dominating Set run in \(2^{O(w^2)}n^{O(1)}\) time. Bergougnoux, Korh...
We prove a generalized quantum Stein lemma for parallel discrimination of an arbitrary finite-dimensional channel against families of alternative channels. The alternatives are compact and convex, closed under tensor products, and contain a faithful replacer. At every fixed type-I error tolerance, the optimal type-II e...
Minbo Gao, Zheng-Feng Ji, Cheng-Hua Liu· 1 citation
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 has widely been used; unfortunately, it is not a simultaneous guarantee. Hill (Ann. Probab., 1987) initiated a complementary approach in which...
Friedgut conjectured that an increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have bounded size, with a bound independent of the dimension and the bias (J. Amer. Math. Soc. 12 (1999)). We prove this conjecture by showing...
If each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using local queries using $\widetilde{O}(\sqrt{\kappa}d)$ local queries, where $\kappa$ is the condition number.
It is proved that Block Orthogonality alone forces both Type Partition and the existence of a single Mal'tsev operation preserving all generated support and row-equivalence relations, and the three-condition characterization collapses to Block Orthogonality.
We prove that counting perfect matchings is $\#P$-complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit interval graphs, and chordal permutation graphs. The monotone result settles the exact-counting complexity left open by Dyer, Jerrum, and M\"ull...
The rank-independent theorem sharpens many later guarantees that inherit their sampling bounds by strengthening the independent STOC 2023 works of Lee and Jambulapati--Liu--Sidford by removing their rank dependence and answering Lee's open question on whether this loss is inherent.
Chenghua Liu, Yuxin Zhang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
