Séminaire Probabilités et Statistiques
Correlation detection in trees for partial graph alignment
Dec. 2021
Intervenant : Marc Lelarge
Institution : INRIA
Heure : 14h00 - 15h00
Lieu : 3L15

Motivated by alignment of correlated sparse random graphs, we study a hypothesis problem of deciding whether two random trees are correlated or not. Based on this tree detection problem, we propose a message-passing algorithm for graph alignment, which is shown to succeed in polynomial time at partial alignment whenever tree detection is feasible. As a result our analysis of tree detection reveals new ranges of parameters for which partial alignment of sparse random graphs is feasible in polynomial time. Joint work with Luca Ganassali and Laurent Massoulié

All (past and future) events