| Orateur(s) | Guillaume Lagarde - Institut de Recherche en Informatique Fondamentale (IRIF) - Université Paris 7,
|
| Titre | Bornes inférieures pour les circuits non-commutatifs : un autre Waterloo de la complexité algébrique ? |
| Date | 14/03/2016 |
| Horaire | 15:10 à 16:10 |
|
| Diffusion | |
| Résume | On ne connait toujours pas de polynôme explicite nécessitant des circuits algébriques non-commutatifs (Circuits NC) de taille superpolynomiale.
Le cadre non-commutatif semble pourtant commode pour montrer de telle borne inférieure car la rigidité de la non-commutativité impose de nombreuses contraintes sur la manière de calculer efficacement. C'est dans ce contexte que Nisan, en 1991, fournit une borne exponentielle sur la taille des ABPs non-commutatifs (Algebraic Branching Programs) calculant le permanent. Nous montrons que ce résultat s'inscrit de manière naturelle comme cas particulier d'un théorème sur les circuits non-ambigus (c'est-à-dire ceux qui ne possèdent qu'un seul type de "parse tree") et proposons quelques pistes afin d'étendre ce résultat à des circuits de plus en plus proche de circuits NC généraux.
(Travaux en commun avec Guillaume Malod et Sylvain Perifel; Nutan Limaye et Srikanth Srinivasan) |
| Salle | 1013 |
| Adresse | Sophie Germain |
