Complexity and Algorithms Working Group

fr / en

The aim of the CoA working group of GdR IM (see also myGDR) is to bring together all researchers in computer science and mathematics interested in the design and analysis of algorithms, i.e. the design of methods and tools for:

• design efficient algorithms, including the identification of new algorithmic paradigms and/or analysis techniques;
• establish lower bounds on computation time, circuit size, approximation factors and qualities, quantity of bits exchanged, etc.

The CoA working group focuses on all forms of algorithms, including sequential, parallel or distributed algorithms, online algorithms, streaming algorithms, approximation algorithms, parameterized algorithms, probabilistic algorithms, quantum algorithms, etc., approached from the joint point of view of design (upper bounds, new paradigms, etc.) and analysis (lower bounds, complexities, etc.). The CoA working group is also interested in algorithms motivated by and applied to alltypes of environments: graphs, networks, biological systems, images, combinatorial objects, etc.

Some of the the leading international CoA-related conferences are: STOC, FOCS, SODA, PODC, SPAA, CCC, ICALP, ESA, DISC, etc., as well as specialized workshops such as WAOA, IPEC, Approx-Random, SIROCCO, etc.

People and laboratories involved in CoA: CoA webpage on myGDR.

• Claire Mathieu (IRIF, Paris), CoA member, received the CNRS silver medal in 2019
• Marthe Bonamy (LaBRI, Bordeaux), member of CoA's scientific committee, received the CNRS bronze medal in 2021
• Carola Doerr (LIP6, Paris), member of CoA's scientific committee, received the CNRS bronze medal in 2022
• Édouard Bonnet (LIP, Lyon), member of CoA's scientific committee, received the CNRS bronze medal in 2023

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

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

• Complexity Days 2023 (Complexity Days 2023), Université Paris Cité, Paris, 13-14 December, 2023
• 3ème Workshop Complexité et Algorithmes (CoA 2023), Sorbonne University, Campus Jussieu, Paris, September 18-20, 2023
• 2ème Workshop Complexité et Algorithmes (CoA 2022), Institut Henri Poincaré (IHP), Paris, 26-28 September 2022
• 1er Workshop Complexité et Algorithmes (CoA 2019), Roscoff, 1-5 April 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.

The registration procedure is as follows:

1. Go to https://mygdr.hosted.lip6.fr/
2. Click on “Laboratoires” to check that your laboratory is present in the database. Please note: If you are not affiliated with any French laboratory, but only with an institution abroad, you must use “Laboratoire à l'étranger”.
   • If your laboratory is present in the database, proceed to point 3.
   • If not, please contact CoA as you cannot register. To this end, please send them your laboratory's full name, acronym and web address. Your laboratory will be added to the list, and you will be notified when this is done, so that you can register.
3. Click on “Register”, and proceed to registration (preferably by professional email), following the instructions for creating a password, and memorizing your login and password.
4. Log in with your login name and password.
5. Fill in your form.
6. Click on “IM”, and the list of GTs appears. Select the WG(s) to which you belong, and you're done.

CoA WG mailing list: add to list.

• Co-leaders: Carola Doerr (LIP6, Paris) and Alantha Newman (G-SCOP, Grenoble)
• CoA board (scientific committee):
  • 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)

The CoA working group has been part of GdR IM since 2012.

Former CoA co-leaders:

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

Former members of the CoA Board (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)