logoMC2

MC2

Models of computation, Complexity, Combinatorics

Team leader: Michaël Rao

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

Postes d'ATER

Deux postes d'ATER à temps plein avec enseignement au Département d'Informatique de l'ENS Lyon et avec recherche au LIP  sont ouverts pour la saison 2024.
L'ensemble des profils de postes de la campagne est en ligne. Les profils sont disponibles sur le site internet de l'ENS de Lyon et et sur Galaxie/ALTAIR.
La clôture des pré-candidatures sur ALTAÏR est fixée au vendredi 09 février à 16h et la clôture pour le dépôt des fichiers de candidature sur DEMATEC au lundi 12 février à 16h.

Contacts:  pour les aspects enseignement Yves Robert et pour les aspects recherche Isabelle Guérin Lassous

University Professor Position

The ENS de Lyon is to open a position for a university professor in computer science, with research at the LIP and teaching in the computer science department. The research profile is open. Given the needs of the department, preference will be given to colleagues likely to teach systems and/or networks, but all applications are welcome, including international ones: teaching can be done in English.

The full description of the position is available on Galaxie. The deadline to apply on Galaxie is 29/03/2024, 16h (Paris time). 

For further information, please contact:
- Eric Thierry, Deputy Director of the Computer Science Department (teaching),
- Nicolas Trotignon, Deputy Director of LIP (research),

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).

Postdoctoral Fellowship 2024
The LIP laboratory is opening a one-year postdoctoral fellowship in Computer Science in Lyon, France.
 
All themes of the laboratory are eligible, in particular: machine learning, computer arithmetic, computer algebra, molecular computing, distributed computing, high performance computing, combinatorics, compilation, complexity, graph theory, quantum computing, logic, computational models, parallelism, proof, scheduling, networks, semantics and verification.
Read More...