Accueil

Responsable : Michaël Rao

Présentation

L'équipe MC2 travaille en informatique théorique au sein du Laboratoire d'Informatique du Parallélisme (LIP) de l'ENS Lyon. 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). We also study the relevant combinatorial structures.

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 or the study of approximation and parameterized algorithms). 

Keywords

Discrete and algebraic algorithms, complexity theory, combinatorics.

 


https://www.ens-lyon.fr/LIP/MC2/ | Saved Saturday, February 24th, 2018 - 11:42 AM