Passer au contenu

/ Research

Je donne

Rechercher

Natural Sciences and Engineering

Pierre McKenzie

La théorie de la complexité du calcul

Professeur titulaire

Faculté des arts et des sciences - Département d'informatique et de recherche opérationnelle

André-Aisenstadt, room 3143

514 343-6176

pierre.mckenzie@umontreal.ca

Secondary number: 514 343-5834 (Télécopieur)
Secondary email: mckenzie@iro.umontreal.ca (Travail)

Profile

Research expertise

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.

Biography

Après des études de premier cycle en physique et une maîtrise dans le domaine des systèmes d’exploitation à l’Université McGill, Pierre McKenzie a consacré une année à faire le tour du monde. Programmeur en Australie en 1978, il se souvient d’une conférence en informatique prononcée à Melbourne par un ancien étudiant d’un certain Steve Cook. 

De retour au pays, il s’inscrit au doctorat à l’Université de Toronto dans le but de pousser plus loin l’étude des systèmes d’exploitation. L’incident de parcours était inévitable : cinq ans plus tard, il détenait un doctorat, en théorie de la complexité, obtenu sous la direction d’Allan Borodin et de Steve Cook, inventeur de la NP-complétude.

Pierre McKenzie est entré en fonction au DIRO en 1984 et il y fait carrière depuis, si l’on exclut une année à l’Université de la Colombie britannique (où ses enfants ont appris l’anglais) et une année à l’Université de Tübingen (où ses enfants, mais pas lui, ont appris l’allemand).

En 2001, il se voyait en confier l’important mandat de diriger le DIRO, qu'il a dirigé jusqu'en 2005.

For more information…

Affiliations and responsabilities

Teaching and supervision

Student supervision

Theses and dissertation supervision (Papyrus Institutional Repository)

2019

Programmes de branchement catalytiques : algorithmes et applications

Graduate : Côté, Hugo
Cycle : Master's
Grade : M. Sc.
2018

Le produit direct de fonctions et les programmes de branchement avec oracle

Graduate : Lavoie, Martin
Cycle : Master's
Grade : M. Sc.
2016

Algorithmique et complexité des systèmes à compteurs

Graduate : Blondin, Michael
Cycle : Doctoral
Grade : Ph. D.
2013

Automates à contraintes semilinéaires = Automata with a semilinear constraint

Graduate : Cadilhac, Michaël
Cycle : Doctoral
Grade : Ph. D.
2012

Complexité raffinée du problème d'intersection d'automates

Graduate : Blondin, Michael
Cycle : Master's
Grade : M. Sc.
2011

Représentation d'un polynôme par un circuit arithmétique et chaînes additives

Graduate : Elias, Yara
Cycle : Master's
Grade : M. Sc.
2009

Analyse de la propriété d'incrémentalité dans le modèle de calcul du programme de branchement

Graduate : Pouliot, David
Cycle : Master's
Grade : M. Sc.
2006

Programmes de génération et machines de Turing algébriques

Graduate : Pilette, Simon
Cycle : Master's
Grade : M. Sc.

Projects

Research projects

2018 - 2026

Lower bounds and derandomizations for branching programs

Lead researcher : Pierre McKenzie
Funding sources: CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Grant programs: PVX20965-(RGP) Programme de subvention à la découverte individuelle ou de groupe
2012 - 2019

THE COMPUTATIONAL COMPLEXITY OF POLYNOMIAL TIME PROBLEMS

Lead researcher : Pierre McKenzie
Funding sources: CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Grant programs: PVX20965-(RGP) Programme de subvention à la découverte individuelle ou de groupe

Outreach

Publications and presentations

Disciplines

  • Computer Science
  • Pure Mathematics

Areas of expertise

  • Finite automata
  • Boolean circuit
  • Formal language
  • Logic
  • Computational complexity theory