BIMSA > BIMSA Lecture Graph alignment for Erdos-Renyi random graphs
Graph alignment for Erdos-Renyi random graphs
Speaker
Mark Rudelson
Time
Tuesday, December 12, 2023 2:00 PM - 3:30 PM
Venue
A3-2a-302
Online
Zoom 361 038 6975 (BIMSA)
Abstract
Consider two copies of the same $G(n,p)$ graph and erase independently the edges of each copy with probability $t < p$. This procedure creates two correlated random graphs. We discuss a randomized algorithm recovering the matching between the vertices of the two graphs for a certain range of parameters.