Consider two copies of the same graph with a large number of vertices. In each copy, we independently delete a few edges. Our aim is to match exactly the vertices of the first and the second copy. This problem originates in particular in social networks, where you know the identities of users in one network and want to recover the identities in another one. This problem is computationally hard in a deterministic setting, so it is often considered for typical, i.e., random graphs. We will discuss a computationally efficient probabilistic algorithm that allows an exact recovery with high probability even if one deletes a small constant proportion of edges.

Joint work with Cheng Mao and Konstantin Tikhomirov.