Séminaires : Séminaire de Logique Lyon-Paris

Equipe(s) : lm,
Responsables :O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, A. Vignati
Email des responsables :
Salle : https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge
Adresse :Sophie Germain
Description

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion


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 ?
Date14/03/2016
Horaire15:10 à 16:10
Diffusion
RésumeOn 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)
Sallehttps://bigbluebutton.imj-prg.fr/b/sil-gwg-gge
AdresseSophie Germain
© IMJ-PRG