Luc Devroye
Université McGill
Domaine : structures abstraites
Programme projet de recherche en équipe
Concours 2010-2011
Comment les outils probabilistes et combinatoires peuvent-ils être utilisés pour attaquer des problèmes en informatique algorithmique? Réciproquement, comment peut-on utiliser les outils venant de l'analyse d'algorithmes dans des preuves probabilistes et combinatoires? En général, ce sont des questions que nous étudions dans notre projet. Nous étudions des problèmes dans le domaine de la probabilité discrète qui sont à saveur algorithmique, et nous prouvons des résultats probabilistes tout en découvrant leur structure combinatoire. De même, nous visons à créer et développer des outils probabilistes pour l'analyse des algorithmes et du comportement des grandes structures de données.
Certains des problèmes spécifiques que nous considérons incluent la percolation "premier-passage" sur les arbres et les graphes, la hauteur des arbres aléatoires, les distances dans les graphes aléatoires, la largeur de prélèvement des chaînes de Markov, et l'utilisation des inégalités de concentration dans l'analyse d'algorithmes et des données aléatoires.