25 Avril - 1 Mai


Retour à la vue des calendrier
Vendredi 29 Avril
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: La hiérarchie du temps logarithmique
Description: Damiano Mazza Pendant le développement de travaux en cours avec Cynthia Kop et Jakob Simonsen j'ai eu l'occasion d'étudier un peu plus de près la classe de complexité LH, ou hiérarchie en temps logarithmique, qui est peut-être plus connue dans sa version non-uniforme sous le nom de AC^0 (circuits booléens avec fan-in arbitraire, de taille polynomiale et profondeur constante). Je vais vous parler un peu de cette hierarchie et plus en particulier de son niveau 0, appelé DLOGTIME, qui constitue probablement l'une des plus petites classes de complexité ayant un emploi non-trivial en complexité algorithmique.