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

Equipe(s) : lm,
Responsables :O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, C. Sureson
Email des responsables :
Salle : salle 2015
Adresse :Sophie Germain
Description

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion


Orateur(s) Thomas Seiller - Laboratoire d'Informatique de Paris-Nord,
Titre Des preuves aux programmes, aux systèmes dynamiques. Perspectives géométriques en complexité algorithmique
Date18/03/2019
Horaire15:10 à 16:10
RésumeLa question de la séparation des classes de complexité fait actuellement face à un manque cruel de méthodes. En effet, de nombreux résultats, appelés barrières, démontrent que les méthodes de preuve connues ne permettront pas de répondre aux questions ouvertes principales. Le principal programme de recherche qui pourrait circonvenir aux barrières est le programme de complexité géométrique de K. Mulmuley. Celui-ci propose de montrer des résultats de séparation via des techniques de géométrie algébrique, et a été introduit après l'obtention d'un résultat de bornes inférieures une variante algébrique de PRAMs, un modèle de machines parallèles ad-hoc.

Cet exposé expliquera comment certaines méthodes récentes venant de la logique permettent de proposer une nouvelle approche à la question de la séparation. Basée sur une interpretation dynamique des programmes, celle-ci suggère une correspondance entre l'expressivité des modèles de calcul étudiés et certains invariants venant de théorie ergodique. Je présenterai également un travail en collaboration avec L. Pellissier, qui a consisté à relire la preuve de séparation ayant inspiré le programme de complexité géométrique via ce nouveau point de vue, faisant apparaitre le rôle de l'entropie topologique des systèmes dynamiques associés aux machines. Au-delà de renforcer l'intuition d'une correspondance entre classes de complexité et certaines classes de systèmes dynamiques, cette abstraction du résultat nous permet également de renforcer le résultat de séparation pour montrer que le problème maxflow (problème complet pour la classe P) n'est pas calculable efficacement par une machine parallèle travaillant avec des entiers.
Sallesalle 2015
AdresseSophie Germain
© IMJ-PRG