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

Equipe(s) : lm,
Responsables :S. Anscombe, O. Finkel, A. Khélif, A. Vignati
Email des responsables : sylvy.anscombe@imj-prg.fr, vignati@imj-prg.fr
Salle : 1013
Adresse :Sophie Germain

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion

Orateur(s) Luc Pelissier - Université de Paris-Est Créteil,
Titre Entropy and Complexity Lower Bounds
Horaire16:00 à 17:15
Diffusion https://u-paris.zoom.us/rec/share/uu80Zbe4lpzNIqlCjkL4P7rn7ep0rc29FPsflY3foV_q6doF42tEDeGLldVrJ4VO.g_i2UH79Qlf9ABPs
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.
AdresseSophie Germain