Membres

Corps professoral

• Michael Blondin — vérification formelle algorithmique, automates, logique, complexité du calcul
• Marc Frappier — méthodes formelles de spécification, sécurité, cybersécurité post-quantique, tests à base de modèles
• Manuel Lafond — bio-informatique, algorithmique, théorie des graphes, complexité paramétrée
• Aïda Ouangraoua — biologie computationnelle et bio-informatique, algorithmique, phylogénétique, structure des ARN
• Nadia Tahiri — bio-informatique, phylogénétique, classification, clustering, algorithmique
• Dave Touchette — informatique quantique, théorie de l’information, complexité de la communication
• Cunlu Zhou — informatique quantique, optimisation, théorie de la complexité, physique quantique

Postdoc

• Elham Torabian (supervision: Dave Touchette + Cunlu Zhou)

Doctorat

• Lida Hooshyar (supervision: Nadia Tahiri + Manuel Lafond)
• Aleksandr Koshkarov (supervision: Nadia Tahiri)
• Quelen Cartellier (supervision: Marc Frappier + Amel Mammar @ Institut polytechnique de Paris)
• Cabrel Feukeng Momo (supervision: Marc Frappier + Amel Mammar @ Institut polytechnique de Paris)
• Vanessa Flügel (supervision: Michael Blondin + Guillermo A. Pérez @ UAntwerpen)
• Théo Lacoste (supervision: Marc Frappier + Régine Laleau @ U. Paris-Est Créteil)
• Lucas Villaume (supervision: Marc Frappier + Guillaume Bonfante @ Université de Lorraine/INRIA)
• Antoine Carrier (supervision: Dave Touchette)
• Alexandre Leblanc (supervision: Cunlu Zhou + Stefanos Kourtis @ IQ)
• Gurleen Padda (supervision: Dave Touchette + Claude Crépeau @ McGill)

Maîtrise

• Caroline Fortier (supervision: Nadia Tahiri)
• Ryan Godin (supervision: Nadia Tahiri)
• Francis Sarrazin (supervision: Manuel Lafond)
• Benjamin Courchesne (supervision: Michael Blondin)
• Samy Chady Khoumsi-Kasmi (supervision: Michael Blondin)
• Hugo Lamoureux (supervision: Marc Frappier)
• Louis Desruisseaux (supervision: Dave Touchette)
• Simon Ducharme (supervision: Dave Touchette)
• Elisabeth Mailhot (supervision: Dave Touchette + Cunlu Zhou)

Stagiaires de premier cycle

• Érika Robidas (supervision: Manuel Lafond)
• Laérian Bontick (supervision: Marc Frappier)
• Yassine Daanoun (supervision: Marc Frappier)
• Eliott Texier (supervision: Michael Blondin)
• Pierre-Étienne Brindle (supervision: Dave Touchette)
• Ludovic Chabot Provencher (supervision: Dave Touchette + Cunlu Zhou)

Axes de recherche

• Algorithmique
• Bio-informatique
• Biologie computationnelle
• Classification
• Clustering
• Complexité du calcul
• Complexité paramétrée
• Cryptographie et sécurité
• Informatique quantique
• Logique
• Méthodes formelles
• Optimisation
• Spécification et raffinement
• Théorie des automates
• Théorie des graphes
• Théorie de l’information
• Théorie du calcul
• Vérification formelle

Cours

• MAT115 – Logique et mathématiques discrètes
• IFT313 – Introduction aux langages formels
• IFT339 – Structures de données
• IFT436 – Algorithmes et structures de données
• IGL501/IGL710 – Méthodes formelles en génie logiciel
• IGL502/IGL752 – Techniques de vérification et de validation
• IFT503/IFT711 – Théorie du calcul
• IFT606 – Sécurité et cryptographie
• IFQ701 – Algorithmes quantiques
• BIN702 – Algorithmes pour la bio-informatique
• BIN704 – Sujets choisis en bio-informatique
• BIN710 – Forage de données pour la bio-informatique
• IFT769 – Sujets choisis en informatique théorique
• IFT800 – Algorithmique
• IFT814 – Cryptographie

Présentations

• 20/04/2026. Jannick Schestag: Phylogenetic Diversity in Networks and with Dependencies (midi-théorie)

  Phylogenetic diversity (PD) is a well-established measure for quantifying the evolutionary diversity of a set of species. It plays a central role in conservation planning and underlies initiatives such as the EDGE of Existence program of the Zoological Society of London and the phylogenetic diversity task force of the IUCN.

  Traditionally, PD is defined on phylogenetic trees: given a set of species A, its PD score is the total weight of all edges on the minimal subtree connecting the root with the leaves in A. However, maximizing phylogenetic diversity on trees alone is biologically not desirable. Thus, we have to find a good trade-off between biological correctness and computational possibility.

  In this talk, we explore two directions of making the model more biologically sound and how it effects computability.

  The first direction we consider is generalizing phylogenetic trees. Modern phylogenetic analyses increasingly rely on phylogenetic networks to model reticulate evolutionary events such as hybridization and horizontal gene transfer. This raises the fundamental question of how PD should be defined in the presence of multiple evolutionary paths.

  Secondly, we survey connecting phylogenetic diversity with considering biological dependencies., that is assuring that protected species may still find prey.

  We discuss the underlying modeling assumptions, how well they capture biological intuition, and the algorithmic challenges they pose. In particular, we compare these notions with respect to their computational tractability and practical applicability, highlighting trade-offs between biological expressiveness and efficient computation.

• 14/04/2026. Michaël Cadilhac: Computability and Transformers: A Circuit Complexity Revival? (midi-théorie)

  Transformer is a neural network architecture that has been central to the recent boom in AI. Starting with its first definition, proposed in 2017 by Vaswani et al., researchers in formal language theory and machine learning have been refining, formalizing, and extending the model into a diverse playground of computational models. Two intertwined questions naturally arise: What are the problems that are computable by these models, and what are the problems they can learn? While the latter question has only seen little formal progress, the former, more amenable question has been the subject of an intense stream of research.

  Core to a lot of results on expressiveness for transformers is a sturdy connection to classical results in Boolean circuit complexity. In this talk, I will present the fundamental definitions of the transformer architecture, and review the expressiveness results in relation to Boolean circuits, first order logic, and temporal logic.

• 23/03/2026. Michael Blondin: Exploring word equations (midi-théorie)

  Word equations play a key role in combinatorics on words similar to that of Diophantine equations in number theory. For example, the equation xyyz = AACGCGT has several solutions, e.g. [x ↦ AA, y ↦ CG, z ↦ T].

  Determining whether a given word equation has a solution is a classical decision problem of theoretical computer science. Word equations have been studied since 1946 and their exact computational complexity remains unknown to this day. Furthermore, the decidability of word equations extended with length constraints, a problem of great interest to the formal verification community, has been open for nearly 60 years.

  In this talk, I will introduce word equations, explain their connection to Hilbert’s tenth problem, and provide insights into techniques for solving (quadratic) word equations.

• 08/05/2025. Norbert Zeh: Sometimes only fools get it right: When cluster reduction isn't safe (séminaire)

  Cluster reduction is a technique that can be used to speed up the construction of phylogenetic networks from sets of trees, or so we thought. Baroni, Semple, and Steel proved that cluster reduction is safe for 2 trees, that is, it preserves the optimality of the constructed network when the input consists of 2 trees. While there are inputs where cluster reduction isn’t applicable, Li and Zeh verified experimentally that on 2-tree inputs, it is the single most important technique for constructing optimal networks efficiently in practice, that not using cluster reduction would be folly. This talk shows that cluster reduction is safe for 3 trees, and briefly mentions how to prove that it is safe also for an arbitrary number of trees if the goal is to compute an optimal tree-child network. I will also discuss how to prove that without restrictions on the network, cluster reduction is not safe for 10 or more trees. With a little extra care, the proof also shows that cluster reduction isn’t safe for 10 or more trees when the goal is to find an optimal orchard. What happens with 4-9 trees is an open problem, but our intuition is that cluster reduction stops being safe already for 4 trees.

  To prove the negative result for 10 trees, we need a set of 5 trees that cannot be displayed by a network with 2n or fewer reticulations, where n is the number of leaves of the input trees. I will discuss how to show that there exists a set of n^eps trees that cannot be displayed by a network with o(n lg n) reticulations. This is interesting because Bordewich and Semple showed that there exists even a tree-based network with O(n lg n) reticulations that displays all trees on n leaves. Our result shows that the number of reticulations increases by only a constant factor when going from n^eps trees to all trees. An extension of this technique that is less fun to discuss in a talk but is based on the same idea proves the result that there exists a set of 5 trees that cannot be displayed by a network with 2n or fewer reticulations.

• 02/04/2025. Stefanos Kourtis: Quantum methods for searching, counting, learning, and simulating physics (séminaire)

  I will present our recent progress in designing quantum methods for the solution of a variety of computational problems spanning combinatorial optimization, model counting, machine learning, and the simulation of quantum many-body phenomena. I will focus on a subset of the following topics, depending on time and interest. I will discuss the quantum alternating operator ansatz (QAOA) and its adaptive variant as a framework for combinatorial optimization. I will introduce an adaptive QAOA algorithm based on Clifford circuits, dubbed ADAPT-Clifford, and show benchmarks on synthetic instances of NP-hard problems, demonstrating performance competitive with an established classical algorithm [1]. I will then discuss QAOA in the context of model counting, a class of problems that underlie probabilistic reasoning. I will introduce VQCount, a sampling-based quantum algorithm for approximate counting, and discuss its expected performance on #P-hard counting problems [2]. Next, I will present a quantum machine learning (QML) framework based on fermionic quantum circuits, which we call FermiML. We apply FermiML to some commonly studied datasets and obtain better classification accuracy than corresponding unrestricted QML models [3]. Finally, I will outline our experimental work on simulating quantum many-body phenomena, specifically measurement-induced entanglement phase transitions, on quantum processors [4,5].

  [1] M. H. Muñoz-Arias, S. Kourtis, A. Blais, Phys. Rev. Research 6, 023294 (2024).

  [2] J. Drapeau, S. Banerjee, S. Kourtis, arXiv:2503.07720 (2025).

  [3] J. Gince, J.-M. Pagé, M. Armenta, A. Sarkar and S. Kourtis, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), Montreal, QC, Canada, 2024, pp. 1672-1678 (2024).

  [4] J. Côté, S. Kourtis, Nat. Commun. 13, 7395 (2022).

  [5] X. Feng, J. Côté, S. Kourtis, B. Skinner, arXiv:2502.01735 (2025).

• 26/03/2025. Benjamin Courchesne: Protocoles de population: robustesse et composabilité (club-info)

  Les protocoles de population constituent un modèle de calcul distribué. S’inspirant des systèmes biologiques, ce modèle repose sur des agents anonymes, disposant d’une mémoire locale constante et non partagée, qui interagissent aléatoirement pour atteindre des objectifs collectifs.

  Durant cette présentation, nous nous pencherons sur la résilience de ces systèmes face à la présence d’erreurs dans leur état initial. Nous examinerons également si ce nouveau concept de robustesse peut servir de cadre d’évaluation pour des automates soumis à des contraintes semi-linéaires.

  Cette présentation se veut ouverte à toutes et à tous, elle prendra donc le temps de poser les bases requises.

• 04/12/2024. Francis Sarrazin: Résolubilité de réparation minimale de cographe par suppressions d'arêtes (séminaire)

  Un langage, ou problème, décrit une famille d’éléments partageant une série de caractéristiques déterminées. Il définit par le même fait l’appartenance ou non d’un élément à cette famille sans ambiguïté possible. Plusieurs problèmes s’appliquent aux graphes, des structures de données visuellement représentées par des nuages de points, appelés nœuds, et des lignes qui les relient, les arêtes. L’attention qui leur est portée n’a rien d’étonnante; les graphes servent à représenter nombre de relations dans divers contextes importants tel le transport, les télécommunications, la biologie et l’intelligence artificielle.

  Pour tout graphe n’appartenant pas à une certaine famille, sa réparation consiste en le retrait de toutes ses erreurs définies par le problème, ou structures interdites, dans l’objectif que le graphe résultant soit membre de ladite famille. Par exemple, un graphe est de la famille des cographes, également appelée P4-Free, s’il ne possède aucun P4 induit. En d’autres mots, un cographe ne doit contenir aucun sous-graphe formé de quatre nœuds et de toutes les arêtes qui les relient, lequel consisterait en un chemin de trois arêtes sans cycle, soit un P4, la structure interdite pour ce cas.

  Une réparation est minimale lorsque réalisée en le moins de modification possible. Les modifications peuvent également être limités à certaines opérations tel que la suppression d’arêtes, et les complexités varient hautement entre chaque interprétation. Même sous ses restrictions, le problème de la résolubilité de réparation minimale de cographe par suppressions d’arêtes est dit NP-Complet. Il a été démontré qu’aucune approche classique permet de le résoudre en temps sous-exponentiel, ce qui introduit l’usage de l’algorithmie à complexité paramétrée tel qu’il sera discuté dans la présentation.

  Définissons H-Free comme l’ensemble des problèmes de réparation minimale par édition menant à l’absence de sous-graphe induits H. Nous présentons un nouvel algorithme récursif compatible sous certaines conditions à la réparation de graphe H-Free. Cet algorithme utilise une sous-fonction modulable adaptée à chaque problème individuel, laquelle reçoit un sous-graphe prime et peut bénéficier des propriétés associées pour retourner un ensemble de solutions partielles dont l’une est garantie optimale. En adaptant cette sous-fonction à la réparation minimale de cographe par suppression d’arêtes, nous renforçons les résultats actuels en termes de complexité paramétrée alors que les limitations, précédemment impossibles à observer, sont maintenant clarifiées. Il est souhaité que ces connaissances nous permettent d’améliorer ces résultats, et de créer de nouvelles ous-fonctions pour d’autres réparations de graphe H-Free.

• 16/09/2024. Lucie Guillou: Safety analysis of parameterised networks with non-blocking rendez-vous and broadcasts (séminaire)

  I will present two recent joint works done with Arnaud Sangnier and Nathalie Sznajder. We study networks of processes that all execute the same finite protocol and communicate synchronously in two different ways: a process can broadcast one message to all other processes or send it to at most one other process. We study two coverability problems with a parameterised number of processes (state coverability and configuration coverability). It is already known that these problem are Ackermann-hard (and decidable) in the general case. This already holds when the processes communicate only by broadcasts. We show that when forbidding broadcasts, the two problems are EXPSPACE-complete. We also study a restriction on the protocol: a Wait-Only protocol has no state from which a process can send and receive messages. We show that without broadcasts, both problems are Ptime-complete in this restriction, and with broadcasts, state coverability is Ptime-complete and configuration coverability PSPACE-complete.