MINDS 2021 Winter Symposium- Dana Yang
Title– Sharp thresholds for the recovery of hidden nearest neighbor graphs
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.