BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Statistical and Computational limits for sparse graph alignment
DTSTART:20220317T140000
DTEND:20220317T150000
DTSTAMP:20260407T195108Z
UID:7eda3dfe8c50cc3b300ebcc11f46c4cff7db668c7bcd798208e71c4f
CATEGORIES:Conferences - Seminars
DESCRIPTION:Luca Ganassali\, Inria\n \nCDM Seminar by Luca Ganassali\, IN
 RIA Paris\n\nAbstract :\nGraph alignment refers to recovering the underlyi
 ng vertex correspondence between two random graphs with correlated edges. 
 This problem can be viewed as an average-case and noisy version of the wel
 l-known graph isomorphism problem.\nFor correlated Erdős-Rényi random gr
 aphs\, we will give insights on the fundamental limits for the planted fo
 rmulation of this problem\, establishing statistical thresholds for partia
 l recovery. From the computational point of view\, we are interested in de
 signing and analyzing efficient (polynomial-time) algorithms to recover e
 fficiently the underlying alignment: in a sparse regime\, we exhibit an lo
 cal rephrasing of the planted alignment problem as the correlation detecti
 on problem in trees. Analyzing this related problem enables to derive a me
 ssage-passing algorithm for our initial task.\nBased on joint works with L
 aurent Massoulié and Marc Lelarge: https://arxiv.org/abs/2002.01258\, h
 ttps://arxiv.org/abs/2102.02685\,https://arxiv.org/abs/2107.07623.\n\nShor
 t bio\nSince September 2019\, I am a Ph.D. student at INRIA Paris under th
 e supervision of Laurent Massoulié and Marc Lelarge. I work in the Dyogen
 e team\, which is a joint team between INRIA and ENS Paris. \nMy research
  interests lie mainly within statistics\, probability theory\, graph theor
 y and machine learning. I am interested in studying procedures for learnin
 g tasks and inference problems with geometry\, symmetries or invariance. M
 ore specifically\, I'm currently looking at inference problems in graphs a
 nd matrices\, such as graph alignment. For these problems\, I am investiga
 ting the information-theoretical and computational thresholds\, as well as
  designing and analyzing new algorithms on random instances to give a bett
 er understanding of the regimes in which they may suceed.\nOther current t
 opics I'm interested in are graph neural networks\, and statistical learni
 ng with optimal transport.\n 
LOCATION:ODY 0 16 https://plan.epfl.ch/?room==ODY%200%2016
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR