Skip to Content

Equipe Algorithmique, Modèles de calcul, Aléa, Cryptographie, Complexité

Présentation de l’équipe

L'équipe AMACC se retrouve d'abord autour de deux concepts génériques, l'algorithme et la complexité, symbolisés par le premier A et le dernier C, qui sous-tendent toutes ses activités. Elle y adopte des points de vue complémentaires. Le premier étudie les modèles de calcul ou la notion de complexité, dans le pire des cas via les classes de complexité (le M pour Modèles de Calcul), tandis que le second travaille dans un cadre aléatoire, avec des modèles probabilistes (le second A pour Aléa).

L'équipe a aussi des spécialités algorithmiques bien marquées: elle travaille en amont de la Protection de l'Information, notamment en codage et cryptographie (le premier C), où elle s'appuie sur ses compétences en théorie de l'information et en arithmétique. Elle s'ouvre désormais aussi à d'autres thématiques, liées à la sécurité (internet des objets ou l'environnement embarqué sécurisé) ou à l'algorithmique du web.

L'équipe organise le séminaire hebdomadaire séminaire Algorithmique, qui cimente l'équipe (voir également ici).

L'équipe co-organise le séminaire Cryptologie & Sécurité (en commun avec le laboratoire de Mathématiques LMNO et Orange Labs.)

Membres

Direction : Julien Clément.

Principaux thèmes de recherche

L'équipe s'organise ainsi selon trois principaux thèmes.

Faits marquants

Nous relevons les principaux résultats scientifiques et les faits marquants suivants qui éclairent et caractérisent bien la vie de notre équipe durant le dernier quinquennal:

  • Nous avons obtenu durant la période, et de manière régulière, des résultats scientifiques bien reconnus: par exemple, en 2011, 2012, 2013 et 2014, nous avons quatre articles acceptés à STACS, sur des thématiques variées et caractéristiques d’AMACC (automates cellulaires, analyse d'algorithmes, combinatoire). La conférence STACS (Symposium on Theoretical Aspects of Computer Science), se situe parmi les cinq conférences internationales en Informatique Théorique les plus « cotées ».
  • Nous avons joué un rôle important dans l'organisation d'un colloque à la mémoire de Philippe Flajolet (1948-2011), et nous faisons partie du comité d'édition des œuvres complètes (sept volumes à paraître chez Cambridge Press, responsabilité d'un volume et de deux chapitres).
  • Nous sommes fortement impliqués dans le GDR Informatique Mathématique:
    • Prise dans son ensemble, l'équipe participe de manière active à beaucoup de groupes de travail de ce GDR (cinq à six sur une vingtaine en tout). Nous avons organisé en particulier les journées annuelles de deux d'entre eux.
    • L'équipe a organisé l'EJCIM 2014 (École Jeunes Chercheurs en Informatique Mathématique); en plus des tâches générales d'organisation, elle a pris en charge trois des cinq cours, et a édité le recueil des cours dans le livre « Une photographie de l'informatique mathématique 2014 ».
    • Deux d'entre nous sommes membres du comité de direction.
    • L'un d'entre nous est responsable du site internet et du serveur de listes, tous deux hébergés par le GREYC.
  • Nous tissons des liens resserrés avec l'Amérique du Sud: Le projet CNRS STIC-AMSUD (Argentine, France, Uruguay) que nous portons depuis 2013 s’est récemment renforcé en automne 2014: nous avons intégré le laboratoire international associé (LIA) INFINIS à Buenos Aires (Argentine) en y créant une nouvelle équipe.
  • L'une d'entre nous est membre du Conseil National du Numérique (proposée par le CNRS) et a notamment participé à la rédaction de deux rapports:
    • Rapport Inclusion (automne 2013): Citoyens d’une société numérique. Accès, Littératie, Médiations, Pouvoir d’agir, Pour une nouvelle politique d’inclusion
    • Rapport éducation (automne 2014): Jules Ferry 3.0. Bâtir une école créative et juste dans un monde numérique.
  • L'équipe s'implique fortement dans la formation des enseignants de l'informatique dans les lycées (Informatique et Sciences du Numérique). En coordination avec le rectorat, elle a contribué à la mise en place de la formation ; elle anime et participe à la formation elle-même.
  • L'un de nous a créé une entreprise, l'entreprise ix-labs ``Algorithms for the social web, adversarial information retrieval, data science, approximate verification' (Sylvain Peyronnet).

Projets nationaux

Nous listons ici les projets ANR auquels nous avons participé (selon cas, porteur du projet, partenaire ou appartenance individuelle d'un ou plusieurs membres de l'équipe)

  • Projet LAREDA «Lattice Reduction Algorithms : Dynamics, Probabilities, Experiments, Applications», 2007-2011 (GREYC porteur, avec IMB (Dijon), IRISA (Rennes), LIP (Lyon), LIRMM (Montpellier).
  • Projet ENUM « Algorithmes et complexité des problèmes d’énumération », 2007-2011 (ANR Blanche, GREYC partenaire).
  • Projet PACE « Pairings and Advances in Cryptology for E-cash~», 2007-2011 (ANR Blanche, GREYC partenaire).
  • Projet WINGS « Widening Interoperability for Networking Global Supply Chains » 2009 - 2011 (partenaire).
  • Projet EMC « Émergence dans les modèles de calcul » 2009-2012 (ANR Blanche, participation individuelle).
  • Projet BOOLE « Quantification des propriétés de structures booléennes avec des méthodes de combinatoire analytique ou des méthodes probabilistes » 2009-2012 (ANR Blanche, GREYC partenaire).
  • Projet MAGNUM « Méthodes algorithmiques de génération aléatoire non uniforme. modèles et applications », 2010-2014 (ANR Blanche, participation individuelle).
  • Projet SIMPATIC « SIM et théorie des couplages pour la sécurité de l'information et des communications », 2012-2015 (GREYC partenaire).
  • Projet DynA3S « DYNamics of gcd algorithms: an Algorithmic, Analytic, Arithmetic, and Symbolic approach », 2013-2016 (ANR Blanche, GREYC partenaire).
  • Projet AGGREG « algorithmes et complexité des problèmes d’énumération », 2014-2017 (participation individuelle)

Plus d'informations sur les ANR du laboratoire : cliquez ici.

Projets internationaux

  • Projet ECOS : collaboration entre la France et l'Uruguay (2009-2012)
  • Projet NSF avec l'Univ. of Colorado: '' Markovian Embeddings for the analysis and computation of patterns in non-markovian random sequences'' (2009-2010)
  • Projet STIC-AMSUD Dynalco (France, Argentine, Uruguay) 2013-2014.
  • Création d'une équipe dans le LIA INFINIS à Buenos Aires (Laboratoire International Associé).

Production scientifique

Rapports d’activités spécifiques

Organisation de manifestations internationales:

  • Colloque LLL+25 en juin 2007 : édition des actes dans un livre chez Springer paru en 2010.
  • Journées "Numbers, sequences, lattices: dynamical analysis of algorithms"  3-4 juin 2010.
  • « Workshop on Coding and Cryptography », (WCC 2011) Paris (France), avril 2011 (participation au comité d'organisation).
  • « Philippe Flajolet and Analytic Combinatorics »}, Conference in the memory of Philippe Flajolet, Paris-Jussieu, 14-15-16 décembre 2011 (participation au comité d'organisation et au comité de programme).
  • «~Journées en l'honneur des 60 ans d'Etienne Grandjean~», Caen, les 18 et 19 décembre 2013.
  • « iSWAG Symposium »}, International Symposium on Web Algorithms, 2-3 juin 2015, Deauville.
Comités de pilotage: STACS (Etienne Grandjean de 2007 à 2012), AofA (Brigitte Vallée).

Organisation de colloques et rencontres nationales

Édition:

  • Journal of Computer and System Sciences: Véronique Terrier éditrice depuis fin 2007. Cette revue existe depuis 1967.
  • RAIRO: Brigitte Vallée éditrice sur la période 2011-2013.

Formation

Les membres de l'équipe interviennent principalement au niveau Master (ou équivalent) dans la spécialité ESECURE du Master (resp. Etienne Grandjean et Patrick Lacharme pour le Master 2, Ali Akhavi pour le Master 1 Informatique).