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

Equipe(s) : lm,
Responsables :O. Finkel, A. Khélif, S. Rideau, T. Tsankov, A. Vignati
Email des responsables :
Salle : Zoom ID: 824 8220 9628; s'inscrire à la liste ou contacter silvain.rideau@imj-prg.fr pour le mot de passe.
Adresse :
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)
SalleZoom ID: 824 8220 9628; s'inscrire à la liste ou contacter silvain.rideau@imj-prg.fr pour le mot de passe.
Adresse
© IMJ-PRG