Pour vous authentifier, privilégiez eduGAIN / To authenticate, prefer eduGAIN
PSCDS Seminars

Looking for Adam in a tree

by Gábor Lugosi (Pompeu Fabra University Barcelona)

Auditorium (LRI, Shannon building (660))


LRI, Shannon building (660)


We discuss algorithms to find the first vertex in large random trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of K vertices, such that, with probability at least 1 − ε, the first vertex is in this set. We show that for any ε, there exist such algorithms with K independent of the size of the tree. The talk is based on joint work with Seb Bubeck and Luc Devroye.