Defence of Doctoral Dissertation: Jean-Yves Moyen

Implicit Complexity in Theory and Practice
Doctorial dissertation by Jean-Yves Moyens

Abstract

Implicit Computational Complexity aims at finding syntactical criteria on programs that guarantee a runtime behaviour (usually, complexity). Ideally, ICC should analyse any program to determine its complexity, possibly even suggesting optimisations. While it is impossible to precisely determine the complexity of all programs, ICC still manages to prove that a wide range of programs run in polynomial time.

This dissertation presents my past and present works in the field of ICC.
The first part groups several journal articles showing incremental advances in ICC: the notion of Quasi-Interpretation and how it can be used for proving various complexity bounds; the notion of Resource Control Graphs and how they can be used for expressing several ICC results in a common language; and the notion of transverse criteria and how they can be used for comparing ICC results.

The second part groups current works studying the set of equivalences between programs, a new direction in ICC that builds on twenty years of research in the field. The extensional equivalence (two programs are equivalent if they compute the same function) plays a central role in Computability. Are there any other equivalences which could play a similarly important role?

The third part shows a possible application of ICC “in real life”. After twenty years and many results, it seems that ideas from ICC are ready to be used in actual compilers. Indeed, it is possible to add some new analysis or optimisations as compiler passes. This opens ways for a fruitful collaboration between two separate research communities.

Official opponents

Professor Simona Ronchi Della Rocca, Dipartimento di Informatica, Università di Torino, Italy
Professor Emeritus Niel Jones, Department of Computer Science, University of Copenhagen, Denmark
Chairman: Professor Mads Nielsen, Department of Computer Science, University of Copenhagen

Unofficial opponents (ex auditorio)

Unofficial opponents must contact the chairman of the defense, Mads Nielsen at madsn@di.ku.dk

For a copy of the assessment Committee’s report and co-author statements, please contant the Faculty Secretariet at sci-fi@science.ku.dk
For a copy of the dissertation, please contact Jean-Yves Moyen at Jean-Yves.Moyen@lipn.univ-paris13.fr

Please note that the entire defense will be recorded.