Équipe Modèles de Calcul et de Complexité (MC2)
|
|
Équipe Modèles de Calcul et de Complexité (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, dont voici un plan d'accès. 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.
Les horaires des exposés à venir ainsi que de plus amples informations sont disponibles sur la page du groupe de travail.
We try to understand the power and limitations of efficient algorithms. Toward this end we design and analyze algorithms, and we set impossibility results (i.e., completeness results or whenever possible unconditional lower bounds).
Algorithms can be sequential, parallel, distributed, synchronous or asynchronous, deterministic, probabilistic or quantum. Efficiency is quantified through complexity measures like computation time or memory requirements or volume of data exchanged. Besides classical sequential machines and in order to focus the attention on one or several of these different aspects of computation, we may consider various models of computation such as, for example, boolean circuits, quantum machines or networks of automata.
Strong attention is given to the study of algorithms on discrete structures and algebraic algorithms.
Various fields of mathematics, in particular combinatorics, are at the heart of this research.
Discrete and algebraic algorithms, complexity theory, combinatorics.