Graph alignment for Erdos-Renyi random graphs
演讲者
Mark Rudelson
时间
2023年12月12日 14:00 至 15:30
地点
A3-2a-302
线上
Zoom 361 038 6975
(BIMSA)
摘要
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.