[Statlist] ETH Young Data Science Researcher Seminar Zurich, Virtual Seminar by Dana Yang, Duke University

[Maurer Letizia]

Dear all

We are glad to announce the following talk in the virtual ETH Young Data Science Researcher Seminar Zurich

"The planted matching problem: Sharp threshold and infinite-order phase transition"  
by Dana Yang, Duke University

Time: Friday, 26 March 2021, 15:00 -​16:00
Place: Zoom at https://ethz.zoom.us/j/92367940258

Abstract: Motivated by the application of tracking moving particles from snapshots, we study the problem of reconstructing a perfect matching hidden in a randomly weighted nxn bipartite graph. The edge set includes every node pair in the hidden matching and each of the other n(n-1) node pairs independently with probability d/n. The weight of each edge is independently drawn from distributions P or Q, depending on whether the edge is in the hidden matching.

In this talk, we establish the information-theoretic threshold for recovering almost all the edges of the hidden matching. We show that the sharp threshold occurs at \sqrt{d}B(P,Q)=1, where B(P,Q) stands for the Bhattacharyya coefficient, resolving the conjecture in [Moharrami et al. 2019, Semerjian et al. 2020]. Furthermore, in the special case of complete exponentially weighted graphs with d=n, P=\exp(\lambda), and Q=\exp(1/n), for which the sharp threshold simplifies to \lambda=4, we prove that when \lambda <= 4-\epsilon, the optimal reconstruction error (the average number of misclassified edges) is \exp(-\Theta(1/\sqrt{\epsilon})), confirming the conjectured infinite-order phase transition in [Semerjian et al. 2020]. This is joint work with Jian Ding, Yihong Wu and Jiaming Xu. The preprint of this work is available at https://arxiv.org/abs/2103.09383.
Best wishes,

M. Azadkia, Y. Chen, G. Chinot, M. Löffler, A. Taeb

Seminar website: https://math.ethz.ch/sfs/news-and-events/young-data-science.html