Short Talk: Robin Khanfir

Starting from an initial root, build a random tree of size $n$ by successively attaching each new vertex to an existing node chosen uniformly at random. If you were given only the final tree, how would you find the root? How easy would it be? In this talk, I will present the best root recovery algorithm and the notion on which it is based: rumor centrality. Then, I will describe the structure of the set of most central vertices and explain how to use it to characterize sharply the algorithm's accuracy. Based on joint work with Louigi Addario-Berry, Catherine Fontaine, Louis-Roy Langevin, and Simone Têtu.