November 2, 2020
Luc Pellissier (LACL)Finding 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.