307 citations · 907 across the 65 of their papers we have counts for
4 papers · 1 filter
Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
Bruce Hajek, Yihong Wu, Jiaming Xu
The binary symmetric stochastic block model deals with a random graph of vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected indepe…
Minimax rates of entropy estimation on large alphabets via best polynomial approximation
Yihong Wu, Pengkun Yang
Consider the problem of estimating the Shannon entropy of a distribution over elements from independent samples. We show that the minimax mean-square error is within univer…
Computational Lower Bounds for Community Detection on Random Graphs
Bruce Hajek, Yihong Wu, Jiaming Xu
This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph , where the edge probability withi…
Dissipation of information in channels with input constraints
Yury Polyanskiy, Yihong Wu
One of the basic tenets in information theory, the data processing inequality states that output divergence does not exceed the input divergence for any channel. For channels witho…