11 citations · 38 across the 20 of their papers we have counts for
21 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…
Submodular Maximization under the Intersection of Matroid and Knapsack Constraints
Yu-Ran Gu, Chao Bian, Chao Qian
Submodular maximization arises in many applications, and has attracted a lot of research attentions from various areas such as artificial intelligence, finance and operations resea…
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…
Fast Sampling of -Matchings and -Edge Covers
Zongchen Chen, Yuzhou Gu
For an integer , a -matching (resp. -edge cover) of a graph is a subset of edges such that every vertex is incident with at most (resp. at l…
Optimal Bounds for Noisy Sorting
Yuzhou Gu, Yinzhan Xu
Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that comparisons are both necessary and sufficient to sort…
Weak Recovery Threshold for the Hypergraph Stochastic Block Model
Yuzhou Gu, Yury Polyanskiy
We study the weak recovery problem on the -uniform hypergraph stochastic block model (-HSBM) with two balanced communities. In HSBM a random graph is constructed by placing h…
Uniqueness of BP fixed point for the Potts model and applications to community detection
Yuzhou Gu, Yury Polyanskiy
In the study of sparse stochastic block models (SBMs) one often needs to analyze a distributional recursion, known as the belief propagation (BP) recursion. Uniqueness of the fixed…
Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
Yuzhou Gu, Zhao Song, Junze Yin +1
Given a matrix , the low rank matrix completion problem asks us to find a rank- approximation of as for …
A Faster Small Treewidth SDP Solver
Yuzhou Gu, Zhao Song
Semidefinite programming is a fundamental tool in optimization and theoretical computer science. It has been extensively used as a black-box for solving many problems, such as embe…
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams +1
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in time, and it is widely open whether it has an time algori…
Stochastic block model entropy and broadcasting on trees with survey
Emmanuel Abbe, Elisabetta Cornacchia, Yuzhou Gu +1
The limit of the entropy in the stochastic block model (SBM) has been characterized in the sparse regime for the special case of disassortative communities [COKPZ17] and for the cl…
Broadcasting on trees near criticality
Yuzhou Gu, Hajir Roozbehani, Yury Polyanskiy
We revisit the problem of broadcasting on -ary trees: starting from a Bernoulli random variable at a root vertex, each vertex forwards its value across binary symme…
Non-linear Log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
Yuzhou Gu, Yury Polyanskiy
Consider the semigroup of random walk on a complete graph, which we call the Potts semigroup. Diaconis and Saloff-Coste computed the maximum of the ratio of the relative entropy an…
A note on spanoid rank
Yuzhou Gu
We construct a spanoid on elements with where . This…
Zero-error communication over adder MAC
Yuzhou Gu
Adder MAC is a simple noiseless multiple-access channel (MAC), where if users send messages , then the receiver receives with addi…
Graph magnitude homology via algebraic Morse theory
Yuzhou Gu
We compute magnitude homology of various graphs using algebraic Morse theory. Specifically, we (1) give an alternative proof that trees are diagonal, (2) identify a new class of di…
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
Lijie Chen, Erik D. Demaine, Yuzhou Gu +3
Since the introduction of retroactive data structures at SODA 2004, a major unsolved problem has been to bound the gap between the best partially retroactive data structure (where…
Some Results on Reversible Gate Classes Over Non-Binary Alphabets
Yuzhou Gu
We present a collection of results concerning the structure of reversible gate classes over non-binary alphabets, including (1) a reversible gate class over non-binary alphabets th…
Generalized equivariant model structures on
Yuzhou Gu
Let be a small category, be the category , or of small categories, acyclic categories, or posets, respectively. Let $\m…