Travaux de recherche

Mon intéret de recherche à long terme est la théorie de la complexité du calcul. Cette théorie vise à ordonner partiellement les problèmes calculatoires selon la quantité de ressources nécessaire et suffisante pour les résoudre. Le temps et la mémoire sont des exemples de ressources. La multiplication de deux entiers et le calcul d'un chemin dans un graphe sont des exemples de problèmes. Est-il plus difficile de calculer un chemin que de multiplier? Une telle question se formule mathématiquement et sa réponse n'est pas connue: elle requiert une preuve que tout algorithme imaginable effectuant le calcul de chemins prendra nécessairement plus de ressources sur de grands graphes que les ressources requises pour multiplier de grands entiers.

En complexité, les conjectures abondent mais les progrès sont lents.

Liste inerte complète de mes publications

au 16 février 2012

Liste de publications (DBLP)

Quelques publications en ligne

Quelques présentations


Quelques publications placées en ligne

Note: les droits d'auteur de plusieurs des publications ci-dessous ont été cédées à la maison d'édition concernée. Toute copie éventuellement faite d'une des publications ci-dessous doit être considérée comme fournie par l'auteur à titre personnel et ne doit servir qu'à l'usage personnel du lecteur.

Quelques présentations