Florent Capelli (Departement of Computer Science and Information Systems at Birkbeck College, London)

Les branching programs forment un ensemble de modèles de calcul assez naturels, décrivant le comportement de nombreux algorithmes de décisions. Dans ces modèles, une fonction booléenne est décrite par un graphe dirigé acyclique dont les nœuds représentent une prise de décision quant à la valeur d’une variable. Plusieurs paramètres peuvent être modifiés afin de les rendre plus ou moins concis, comme borner le nombre d’occurrences des variables le long d’un chemin ou ajouter des nœuds représentant des choix non déterministes.

Dans cet exposé, nous commencerons par présenter ce modèle de calcul et ses variantes. Nous montrerons ensuite une méthode très générale pour prouver des bornes inférieures pour ces modèles et exhiberons certaines bornes inférieures non polynomiales classiques de la littérature. On remarquera que ces bornes inférieures utilisent toujours des propriétés algébriques des fonctions et reposent sur des arguments non combinatoires. Nous présenterons ensuite un lemme très simple concernant la proportion de vertex cover contenant un ensemble donné de sommets dans les graphes de degré borné et expliquerons comment l’utiliser pour prouver simplement d’aussi bonnes bornes inférieures en utilisant seulement des constructions classiques dans les graphes.

Cette dernière partie utilise plusieurs travaux indépendants réalisés en collaboration avec Simone Bova, Stefan et Friedrich Slivovsky d’une part et avec Oded Lachish et Igor Razgon d’autre part.