Orateur
Description
L'objectif de ce cours est de faire découvrir un pendant algorithmique des résultats présentés dans les cours d'Omid Amini et Mathieu Piquerez en théorie des matroïdes, en nous concentrant sur des algorithmes récents d'Anari, Liu, Oveis Gharan et Vinzant permettant de compter et d'échantillonner de façon très efficace des bases de matroïdes. Nous commençons par un survol des enjeux de la théorie des matroïdes en informatique théorique, qui permettent de généraliser le cadre désormais très bien compris des graphes à des contextes plus larges. Nous introduisons ensuite les polynômes log-concaves (également connus sous le nom de polynômes Lorentziens dans les travaux de Branden et Huh), dont les définitions d'apparence simple cachent des propriétés très riches qui sont intimement liées aux sujets traités dans les deux autres cours. Ces propriétés en font un outil très efficace pour résoudre de multiples problèmes combinatoires et algorithmiques, et nous esquisserons comment elles sont exploitées dans les algorithmes sus-cités pour résoudre des problèmes d'informatique théorique ouverts depuis une trentaine d'années.
