In a recent paper, the author has shown how Interaction Graphs models for linear logic can
be used to obtain implicit characterisations of non-deterministic complexity classes. In this …

The author introduced models of linear logic known as “Interaction Graphs” which
generalise Girard's various Geometry of Interaction constructions. In this work, we establish …

This paper presents a new semantic method for proving lower bounds in computational
complexity. We use it to prove that maxflow, a PTIME complete problem, is not computable in …

Lower bounds. Complexity theory has traditionally been concerned with proving separation
results. Among the numerous open separation problems lies the much advertised Ptime vs …

Based on work on realisability models for linear logic, the author recently proposed a new
approach of implicit computational complexity. He showed how to characterise in this way a …

This thesis aims to establish new connections between two distinct fields within theoretical
computer science. The first is automata theory, whose objects of study are models of …

This paper presents a new abstract method for proving lower bounds in computational
complexity. Based on the notion of topological entropy for dynamical systems, the method …

Éléments de contexte scientifique local: Cette these encadrée par Stefano Guerrini, Thomas
Seiller, et Geoffroy Couteau porte sur un theme de la théorie de complexité” …