Séminaires : Séminaire Général de Logique

Equipe(s) : lm,
Responsables :S. Anscombe, V. Bagayoko, D. Basak, H. Fournier, A. Vignati
Email des responsables : sylvy.anscombe@imj-prg.fr, bagayoko@imj-prg.fr, basak@imj-prg.fr, fournier@imj-prg.fr, vignati@imj-prg.fr
Salle : 1013
Adresse :Sophie Germain
Description

Archives


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)
Salle1013
AdresseSophie Germain
© IMJ-PRG