
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.

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.
- P
McKenzie, M
Thomas,
H
Vollmer:
Extensional
Uniformity for Boolean Circuits. CSL
2008
- A
Gál,
M
Koucký,
P McKenzie: Incremental
Branching Programs.
Theory
Comput. Syst. 2008.
- A.
Finkel, P. McKenzie et C. Picaronny, A
Well-Structured Framework for Analysing Petri Net Extensions, Information and
Computation, 195, 1-2, pp. 1-29, 2004.
- P. McKenzie, L'informatique, du mammouth au
FMI , dans L'Autre Forum, vol. 8, no. 2,
février 2004, 5-8.
- P.
McKenzie et K. Wagner, The Complexity of
Membership Problems for Circuits over Sets of Natural Numbers, Proc.
2003 Symp. on Theoretical Aspects of Computer Science (STACS) ,
Berlin, mars 2003. Version
journal soumise en octobre 2003.
- Birgit
Jenner, Johannes
Köbler, Pierre McKenzie, Jacobo
Torán: Completeness results for graph isomorphism. JCSS
66(3): 549-566 (2003).
- Markus
Holzer, Pierre McKenzie: Alternating and empty alternating auxiliary
stack automata. TCS
1-3(299): 307-326 (2003).
- Clemens
Lautemann, Pierre McKenzie, Thomas
Schwentick, Heribert
Vollmer: The Descriptive Complexity Approach to LOGCFL. JCSS
62(4): 629-652 (2001), version étendue de The Descriptive
Complexity Approach to LOGCFL, Proc. 1999 Symp. on Theoretical
Aspects of Computer Science (STACS), Trier, mars 1999.
- David
A. Mix Barrington, Peter
Kadau, Klaus-Jörn
Lange, Pierre McKenzie: On the Complexity of Some Problems on Groups
Input as Multiplication Tables. JCSS
63(2): 186-200 (2001), version étendue de On the
Complexity of Some Problems on Groups Input as Multiplication Tables, Proc.
15th IEEE Conference on Computational Complexity (CCC'2000) ,
Florence, juillet 2000.
- P. McKenzie, H. Vollmer, et K. Wagner, Arithmetic
circuits and polynomial replacement systems, Proc. 20th Intern.
Foundations of software technology and theoretical computer science
conference (FSTTCS'2000), New Delhi, Springer LNCS 1974, décembre
2000.
- K.-J. Lange, P. McKenzie et A. Tapp, Reversible space
equals deterministic space, J. Computer and System Sciences (2000),
pp. 354-367. October
1998 version.
- M. Holzer et P. McKenzie, Alternating and
Empty Alternating Auxiliary Stack Automata, Proc. 25th Symp. on
Math. Foundations of Computer Science (MFCS'00), Bratislava, août
2000. Soumis à Theoretical Computer Science
- D. Barrington, P. McKenzie, C. Moore, P. Tesson et D.
Thérien, Equation Satisfiability and Program Satisfiability for Finite
Monoids, Proc. 25th Symp. on Math. Foundations of Computer Science
(MFCS'00), Bratislava, août 2000. March 2000
version
- P. McKenzie, T. Schwentick, D. Thérien, et H. Vollmer, The
many faces of a translation, Proc. 27th Intern. Colloq. on
Automata, Languages and Programming (ICALP'2000) , Genève, juillet
2000.
- C. Damm, M. Holzer, et P. McKenzie, The complexity of
tensor calculus (May 2000), soumis à Computational Complexity.
Version courte dans Proc. 15th IEEE Conference on Computational
Complexity (CCC'2000) , Florence, juillet 2000.
- P.
McKenzie, La complexité apprivoisée, article de vulgarisation dans le
cahier spécial Mathématiques AN 2000 de l'ACFAS, mai 2000 pp.
14-17.
- R. Raz et P. McKenzie, Separation of the Monotone NC
Hierarchy, Combinatorica 19, 3 (1999), pp. 403-435. March 1998 version
- P. McKenzie, K. Reinhardt et V. Vinay, Circuits and
context-free languages, Proc. Fifth Annual International Computing
and Combinatorics Conference (COCOON) , Tokyo, juillet 1999.
- A. Baziramwabo, P. McKenzie et D. Thérien, Modular temporal
logic, Proc. 1999 IEEE Conference on Logic in Computer Science
(LICS) , Trento, juillet 1999.
- K.-J. Lange et P. McKenzie, On the Complexity
of Free Monoid Morphisms, Proc. 1998 Annual Conference on
Algorithms and Computation (ISAAC 98), Taejon, décembre 1998.
- B. Jenner, P. McKenzie et J. Toràn, A note on the
hardness of tree isomorphism, Proc. 13th IEEE Conference on
Computational Complexity (CCC'1998) , (1998), pp. 101-105.
- B. Jenner, K.-J. Lange et P. McKenzie, Tree isomorphism
and some other complete problems for deterministic Logspace,
publication #1059, DIRO, Université de Montréal, mars 1997.
- H. Caussinus, P. McKenzie, D. Thérien, et H. Vollmer, Nondeterministic
NC1 computation, Journal of Computer and System Sciences, 57,
2, pp. 200-212, 1998.
- A. Finkel et P. McKenzie, Verifying identical
communicating processes is undecidable, Theoretical Computer
Science, 174, pp. 217-238, 1997.
- B. Jenner, P. McKenzie, et D. Thérien, Logspace and
logtime leaf languages, Information and Computation 129, 1, pp.
21-33, août 1996.

- The Complexity of
Membership Problems for Circuits over Sets of Natural Numbers, Dagstuhl
seminar, octobre 2002.
- The many
faces of a translation, 27th International Colloquium on Automata,
Languages and Programming , Genève, juillet 2000.
- On the
Complexity of Some Problems on Groups Input as Multiplication Tables, 15th
IEEE Conference on Computational Complexity , Florence, juillet 2000.
- Arithmetic
circuits and polynomial replacement systems, Colloque
DIMACS-DIMATIA , Université Rutgers, New Jersey, mai 1999.
