logoMC2

MC2

Models of computation, Complexity, Combinatorics

Team leader: Stéphan Thomassé

Keywords: discrete and algebraic algorithms, complexity theory, combinatorics

 

Our main objective is to understand the power and limitations of efficient algorithms, considering various models of computation: sequential model, algebraic complexity, symbolic dynamics, quantum computing, molecular programming. The main mathematical tools of our research are combinatorics and algebra.

  • Algebraic complexity
    We study an algebraic analogue of the P versus NP problem based on the computation model of arithmetic circuits. These circuits are made of addition and multiplication gates (instead of boolean gates in boolean circuits) and therefore compute polynomials.

  • Graph theory and algorithms
    Our research deals with structural properties of graphs, which can then be used in order to design new algorithmic tools (e.g.: polynomial exact or approximation algorithms, parameterized or moderately exponential algorithms). Among other graph problems, we focus on the chromatic number, the independence number, or the maximum clique number of a graph.

  • Quantum information
    Quantum devices have a great potential for information technology. One of the main bottlenecks in building quantum computers is the presence of noise. Our research aims at designing ways to perform computation and communication efficiently using noisy devices. This includes designing error-correcting codes and fault-tolerant schemes.

  • Symbolic dynamics
    One of our goals is to explore computational and combinatorial aspects of symbolic dynamics on finitely generated groups. We aim to tackle three difficult questions: first, characterizing finitely generated groups with decidable Domino problem; second, understanding which groups admit aperiodic SFTs ; third, defining powerful tools to compute the entropy of 2D subshifts.

Latest News

 
Post-Doc Position 2025

The LIP laboratory is opening a one-year post-doctoral fellowship in Computer Science at the ENS Lyon, France. [more info]


Postes d'ATER

 Trois postes d'ATER en informatique sont mis au concours au Département d’Informatique (DI) de l'ENS de Lyon pour l'année universitaire 2025–2026.

L’enseignant·e recruté·e assurera principalement des TD et TP dans les formations dispensées en L3, M1, et préparation à l’agrégation, auprès des étudiant·e·s en informatique de l'ENS de Lyon :  https://informatique.ens-lyon.fr/fr

Les candidatures sont sollicitées sur toutes les thématiques du laboratoire de l'informatique du parallélisme (LIP) :  https://www.ens-lyon.fr/LIP/index.php/research

Contacts Enseignement :
Michele Pagani michele.pagani@ens-lyon.fr
Eric Thierry eric-thierry@ens-lyon.fr

Contacts Recherche :
Isabelle Guérin Lassous isabelle.guerin-lassous@ens-lyon.fr
Nicolas Trotignon nicolas.trotignon@ens-lyon.fr
En suivant ce lien, vous trouverez dans l'onglet Research, le détail de toutes les équipes et leurs axes de recherche : https://www.ens-lyon.fr/LIP/index.php/research

Comment candidater ? Pour connaitre la liste des documents à déposer : https://www.ens-lyon.fr/lecole/travailler-lens-de-lyon/recrutement-des-enseignants-et-des-chercheurs/recrutement-dater

Candidatures sur Galaxie/ALTAIR/ODYSSEE du 15 janvier jusqu'au jeudi 13 février, 16h et dépôt du dossier PDF via DEMATEC jusqu'au lundi 17 février, 16h.


Poste d'ingénieur de recherche au LIP en mobilité interne

Le Laboratoire de l'Informatique du Parallélisme propose un poste d'ingénieur de recherche CNRS ouvert en mobilité interne (accessible à tout titulaire de la fonction publique), pour des activités en lien avec l'expérimentation réseau et/ou le développement Rust. Pour plus d'information, voir la fiche de poste.

Contacts: Isabelle Guérin Lassous (isabelle.guerin-lassous@ens-lyon.fr) ou Simon Delamare (simon.delamare@ens-lyon.fr).