4 papers
Exact reconstruction thresholds on hypertrees over a symmetric binary alphabet
Yuzhou Gu
We establish the exact reconstruction thresholds for a class of broadcasting models on hypertrees over a symmetric binary alphabet. As a consequence, we show that the condensation…
A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions
Yuzhou Gu, Xin Li, Yinzhan Xu
We study the query complexity of Boolean functions in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In th…
A Counterexample to the Gaussian Completely Monotone Conjecture
Yuzhou Gu, Mark Sellke
We provide an explicit probability measure on for which the fifth time derivative of the entropy along the heat flow is positive at some time. This disproves the Gauss…
Faster Algorithms for Structured Linear and Kernel Support Vector Machines
Yuzhou Gu, Zhao Song, Lichen Zhang
Quadratic programming is a ubiquitous prototype in convex programming. Many machine learning problems can be formulated as quadratic programming, including the famous Support Vecto…