University of Connecticut

Events Calendar

Probability And Data Science Colloquium

Thursday, April 8, 2021
2:00pm – 3:00pm

Storrs Campus
Online

Speaker: Yihong Wu (Yale University)

Title: Recent results in planted assignment problems

Abstract: Motivated by applications such as particle tracking, network de-anonymization, and computer vision, a recent thread of research is devoted to statistical models of assignment problems, in which the data are random weight graphs correlated with the latent permutation. In contrast to problems such as planted clique or stochastic block model, the major difference here is the lack of low-rank structures, which brings forth new challenges in both statistical analysis and algorithm design.

In the first half of the talk, we discuss the linear assignment problem, where the goal is to reconstruct a perfect matching planted in a randomly weighted bipartite graph, whose planted and unplanted edge weights are independently drawn from two different distributions. We determine the sharp threshold at which the optimal reconstruction error (fraction of misclassified edges) exhibits a phase transition from imperfect to perfect. Furthermore, this phase transition is shown to be of infinite-order in the special case of exponential weight distributions, confirming the conjecture in [Semerjian et al. 2020]. The negative result is shown by proving that, below the threshold, the posterior distribution is concentrated away from the hidden matching by constructing exponentially many long augmenting cycles.

In the second half of the talk, we discuss the quadratic assignment problem (random graph matching), where the goal is to recover the hidden vertex correspondence between two edge-correlated Erdos-Renyi graphs. We prove that there exists a sharp threshold, above which one can correctly match all but a vanishing fraction of the vertices and below which matching any positive fraction is impossible, a phenomenon known as the "all-or-nothing" phase transition. The proof builds upon a tight characterization of the mutual information via the truncated second-moment method and an appropriate "area theorem".

This talk is based on joint work with Jian Ding, Jiaming Xu, Dana Yang and Sophie Yu. Preprints available at: https://arxiv.org/abs/2103.09383, https://arxiv.org/abs/2008.10097, https://arxiv.org/abs/2102.00082.

Contact:

Zhongyang Li

Discrete Mathematics & Statistical Mechanics Seminar (primary), College of Liberal Arts and Sciences, UConn Master Calendar

Control Panel