MINDS 2021 Winter Symposium- Dana Yang
Abstract– Motivated by applications such as discovering strong ties in social networks and assembling genome subsequences in biology, we study the problem of recovering a hidden nearest neighbor (NN) graph in a complete graph, whose edge weights are independent and are distributed according to P for edges in the hidden NN graph and Q otherwise. This model incorporates the celebrated Watts-Strogatz small-world graph as a special case. For both the exact and almost exact recovery problems, we characterize the sharp information-theoretic limits, which are governed by two divergence measures between P and Q. I will highlight the key proof strategies and provide some intuition behind the sharp thresholds, with the help of a lot of pictures.
I will also briefly discuss two other exciting projects on 1) Convex support estimation from noisy measurements and 2) Bayesian de-biasing and posterior asymptotic normality in the high-dimensional sparse linear model.