Groupe de Travail Complexité et algorithmes du GdR IM

Présentation

L’objectif du GT CoA du GdR IM est de rassembler l'ensemble des chercheurs et chercheuses en informatique et mathématique intéressés par la conception et l'analyse d'algorithmes, c'est-à-dire la conception de méthodes et d’outils pour :

  • concevoir des algorithmes efficaces, incluant la mise en évidence de nouveaux paradigmes algorithmiques et/ou de nouvelles techniques d’analyse ;
  • établir des bornes inférieures sur le temps de calcul, la taille de circuits, les facteurs et qualités d’approximation, la quantité de bits échangés, etc.

Le GT CoA se focalise sur toutes les formes d'algorithmes, incluant les algorithmes séquentiels, parallèles ou distribués, les algorithmes online, les algorithmes de streaming, les algorithmes d'approximation, les algorithmes paramètres, les algorithmes probabilistes, les algorithmes quantiques, etc., abordé du point de vue conjoint de la conception (borne supérieures, nouveaux paradigmes, etc.) et de l'analyse (bornes inférieures, complexités, etc.). Egalement, le GT CoA est intéressé par les algorithmes motivés par et appliqués à tous types d'environnements : graphes, réseaux, systèmes biologiques, images, objets combinatoires, etc.

Parmi les conférences phares relatives à CoA au niveau international, on peut citer : STOC, FOCS, SODA, PODC, SPAA, CCC, ICALP (tracks A and C), ESA, DISC, etc., ainsi que différents workshops spécialisés comme WAOA, IPEC, Approx-Random, etc.

Activités

Laboratoires et équipes de recherche impliqués dans CoA

Organisation

Note : De 2012 à 2017, les co-responsables du GT étaient Cyril Gavoille et Nicolas Schabanel.