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)

Europe/Paris
Auditorium (LRI, Shannon building (660))

Auditorium

LRI, Shannon building (660)

https://www.lri.fr/info.pratiques.php
Description

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.