Groupe de Travail Complexité et Algorithmes

fr / en

L’objectif du GT CoA du GdR IM (voir également myGDR) 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étrés, 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, ESA, DISC, etc., ainsi que différents workshops spécialisés comme WAOA, IPEC, Approx-Random, SIROCCO, etc.

Personnes et laboratoires impliqués dans CoA: CoA sur myGDR.

• Claire Mathieu (IRIF, Paris), membre de CoA, a reçu la médaille d'argent du CNRS en 2019
• Marthe Bonamy (LaBRI, Bordeaux), membre du conseil scientifique de CoA, a reçu la médaille de bronze du CNRS en 2021
• Carola Doerr (LIP6, Paris), membre du conseil scientifique de CoA, a reçu la médaille de bronze du CNRS en 2022
• Édouard Bonnet (LIP, Lyon), membre du conseil scientifique de CoA, a reçu la médaille de bronze du CNRS en 2023

• 4ème Workshop Complexité et Algorithmes (CoA 2024), Institut Henri Poincaré (IHP), Paris, 25-27 novembre 2024

• Workshop on Matroid-Constrained Optimization Problems, Institut Henri Poincaré (IHP), Paris, 2-3 avril, 2024

• Complexity Days 2023 (Complexity Days 2023), Université Paris Cité, Paris, 13-14 decembre 2023
• 3ème Workshop Complexité et Algorithmes (CoA 2023), Sorbonne University, Campus Jussieu, Paris, 18-20 septembre 2023
• 2ème Workshop Complexité et Algorithmes (CoA 2022), Institut Henri Poincaré (IHP), Paris, 26-28 septembre 2022
• 1er Workshop Complexité et Algorithmes (CoA 2019), Roscoff, 1-5 avril 2019
• Journée 2 octobre 2018 (IRIF, Paris) programme et exposés
• Journées 27-28 novembre 2017 (LIP, Lyon) programme et exposés
• Journées 28-29 novembre 2016 (LaBRI, Bordeaux) programme et exposés
• Journées 23-24 novembre 2015 (LaBRI, Bordeaux) programme et exposés
• Journées 10-12 septembre 2014 (LIAFA, Paris) programme et exposés
• Journées 19-20 novembre 2013 (LIAFA, Paris) programme et exposés
• Journées 21-22 novembre 2012 (ESPCI, Paris) programme et exposés

• 8th Conference on Highlights of Algorithms, Charles University, Prague, Czechia, June 2-4, 2023
• 10th workshop of the French-Israeli Laboratory on Foundations of Computer Science (FILOFOCS), Université Paris Cité (Site Odéon), May 9-11, 2023.
• 7th Conference on Highlights of Algorithms, London, June 1-3, 2022
• 6th Conference on Highlights of Algorithms, The London School of Economics and Political Science (virtual), May 31 - June 3, 2021.
• Cours Algorithmes quantiques, Frédéric Magniez, chaire annuelle Informatique et sciences numériques du Collège de France, Avril-Juin 2021.
• IGAFIT algorithmic colloquium, starting Oct 1st, 2020
• 5th Conference on Highlights of Algorithms, ETH Zurich (virtual), Aug 31 - Sept 2, 2020
• 8th workshop of the French-Israeli Laboratory on Foundations of Computer Science (FILOFOCS), Tel-Aviv University, November 26-28, 2019.
• 4th Conference on Highlights of Algorithms, University of Copenhagen, June 14-16, 2019.
• 7th workshop of the French-Israeli Laboratory on Foundations of Computer Science (FILOFOCS), Paris , Oct 3-5, 2018.
• 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Paris , Oct 7-9, 2018.
• Workshop on Emergent Algorithms and Network Dynamics (WENDY), Paris , Oct 10-11, 2018.
• 3rd Conference on Highlights of Algorithms, Amsterdam, June 4-6, 2018.
• Workshop on approximation algorithms and networks, Paris, 7 juin 2018.

La procédure d’inscription est la suivante :

1. Allez sur https://mygdr.hosted.lip6.fr/
2. Cliquez sur « Laboratoires » afin de vérifier que votre laboratoire est présent dans la base. Attention : Si vous n'êtes affilié à aucun laboratoire français, mais uniquement à une institution à l'étranger, vous devrez utiliser « Laboratoire à l'étranger ».
   • Si votre laboratoire est présent dans la base, alors passez au point 3.
   • Sinon, merci de contacter les responsables de CoA car vous ne pouvez pas vous inscrire. A cette fin,leur envoyer le nom complet de votre laboratoire, son acronyme, et son adresse web. Votre laboratoire sera rajouté dans la liste, et vous serez notifié lorsque ce sera fait, afin que vous puissiez vous inscrire.
3. Cliquer sur « S’inscrire », et procéder à l’inscription (email professionnel de préférence) en respectant les consignes de création de mot de passe, et en mémorisant vos login et mot de passe.
4. Connectez vous avec votre nom de login de votre mot de passe.
5. Remplir votre fiche.
6. Cliquer sur « IM », et la liste des GT apparait. Sélectionnez le ou les GTs auxquels vous appartenez, et c’est fini.

Liste de diffusion du GT CoA : ajout à la liste.

• Responsables : Carola Doerr (LIP6, Paris) et Alantha Newman (G-SCOP, Grenoble)
• Bureau du GT CoA (conseil scientifique) :
  • Marthe Bonamy (LaBRI, Bordeaux)
  • Edouard Bonnet (LIP, Lyon)
  • Jérémie Chalopin (LIS, Marseille)
  • Vincent Cohen-Addad (Google, France)
  • Monika Csikos (IRIF, Paris)
  • Christoph Dürr (LIP6, Paris)
  • Laurent Feuilloley (LIRIS, Lyon)
  • Joanna Fijalkow (LABRI, Bordeaux)
  • George Giakkoupis (IRISA, Rennes)
  • Bruno Grenet (LJK, Grenoble)
  • Sophie Huiberts (LIMOS, Clermont-Ferrand)
  • Frédéric Magniez (IRIF, Paris)
  • Arnaud de Mesmay (LIGM, Paris)
  • Moritz Muhlenthaler (G-SCOP, Grenoble)
  • Nicolas Nisse (Inria et I3S, Sophia Antipolis)
  • Bertrand Simon (CC-IN2P3, Lyon)
  • Sebastien Tavenas (LAMA, Chambery)
  • Tatiana Starikovskaya (DIENS, Paris)
  • Nguyen Kim Thang (LIG, Grenoble)
  • Adrian Vladu (IRIF, Paris)
  • Hang Zhou (Ecole Polytechnique, Palaiseau)

Le GT CoA existe depuis 2012 au sein du GdR IM.

Les anciens responsables du GT CoA étaient :

• 2018-2023 : Pierre Fraigniaud (IRIF, Paris)
• 2012-2017 : Cyril Gavoille et Nicolas Schabanel

Anciens membres du Bureau GT CoA (2018-2023) :

• Cristina Bazgan (LAMSADE, Paris)
• Carola Doerr (LIP6, Paris)
• Emmanuel Jeandel (LORIA, Nancy)
• Eunjung Kim (LAMSADE, Paris)
• Loris Marchal (LIP, Lyon)
• Alantha Newman (G-SCOP, Grenoble)