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

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

Archives


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