Skip to content. | Skip to navigation

Personal tools
Log in
Sections
You are here: Home Research Research teams MC2 - Modèles de Calcul et Complexité

MC2 - Modèles de Calcul et Complexité

Disciplines Computer Science, Mathematics
Research fields Algebra, Combinatorics, Complexity, Graphs
Supporting organisms CNRS, ENS Lyon
Geographical location ENS (Campus Charles Mérieux)
Lab LIP
Team leader Nicolas Trotignon
Webpage http://www.ens-lyon.fr/LIP/MC2/

 

L'équipe MC2 travaille en informatique théorique au sein du Laboratoire d'Informatique du Parallélisme (LIP) de l'ENS Lyon. Elle est située dans les locaux de l'IXXI. Les principaux thèmes de recherche sont la théorie de la complexité, l'algorithmique sur les structures discrètes et les problèmes algébriques, la combinatoire.

Research
In our research we aim to understand the power and limitations of efficient algorithms. To this end, we design and analyse algorithms, and set impossibility results (completeness results or, when possible, unconditional lower bounds).
Various models of computation can be considered to allow different features in the algorithms (eg, sequential vs parallel, synchronous vs asynchronous, deterministic vs probabilistic or quantum). Various complexity measures can be considered to quantify efficiency, such as time, space, communications.
Among the several fields of mathematics at the heart of this research, our team focuses on algebra and combinatorics. Both of these areas are a source of algorithmic problems which play key roles in the architecture of complexity theory (eg, the complexity of computing matrix permanents or graph colourings). Both areas also provide mathematical tools which are essential to proving theorems in complexity theory (eg, advanced linear algebra and graph theory for de-randomization, for the PCP theorem, or in the study of  parameterized complexity).

Keywords
Discrete and algebraic algorithms, complexity theory, combinatorics.