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) Luc Pelissier - Université de Paris-Est Créteil,
Titre Entropy and Complexity Lower Bounds
Date07/10/2020
Horaire16:00 à 17:15
Diffusion
RésumeFinding lower bounds in complexity theory has proven to be an extremely difficult task. We analyze three proofs of lower bounds that use techniques from algebraic geometry through the lense of dynamical systems. Interpreting programs as graphings – generalizations of dynamical systems due to Damien Gaboriau that model Girard's Geometry of Interaction, we show that the three proofs share the same structure and use algebraic geometry to give a bound on the topological entropy of the system representing the program. This work, joint with Thomas Seiller, aims at proposing Geometry of Interaction derived methods to study dynamical properties of models of computation beyond Curry-Howard.
SalleZoom ID: 824 8220 9628; s'inscrire à la liste ou contacter silvain.rideau@imj-prg.fr pour le mot de passe.
Adresse
© IMJ-PRG