Équipe thématique Pôle Algorithmes et structures discrètes Algorithmes et complexité Responsable Sophie Laplante Intranet of AlgoComp group (for permanent members) Thèmes de recherche La théorie des algorithmes efficaces est le socle commun de nos axes de recherche, à la fois en calcul classique et quantique. Nous cherchons à relever les défis algorithmiques émergeants et à comprendre les limites des nouveaux modèles de calcul. Nous identifions des problèmes centraux de l’algorithmique, puis nous élaborons et analysons des solutions efficaces tout en cherchant à montrer leur optimalité en établissant des bornes inférieures sur la complexité des problèmes traités. En calcul classique, nous étudions plus particulièrement les modèles de calcul qui considèrent divers accès restreints à leur entrée, dont les algorithmes de streaming, en ligne, distribués ou encore de property testing. Le développement et l’étude d’outils probabilistes d’approximation est alors souvent nécessaire pour concevoir des algorithmes restant efficaces. Nous étudions aussi les aspects algorithmiques des systèmes distribués, allant du calcul en réseau à de nouvelles approches dans le contexte du comportement collectif des animaux. Dans ce dernier cas, nous collaborons en parallèle avec des biologistes expérimentaux afin de valider notre méthodologie et nos prédictions. En calcul quantique, nous cherchons à mieux cerner l’apport de l’information quantique pour le calcul, la cryptographie et la communication. Nous sommes aussi impliqués dans plusieurs réalisations expérimentales et partenariats industriels, qui complémentent notre expertise théorique et notre positionnement international. Pour en savoir plus : Calcul quantique à l'IRIF. L’échange réciproque d’idées et techniques entre tous ces modèles de calcul est une caractéristique importante des recherches menées au sein de notre groupe. Nous faisons appel à des outils issus de la théorie de la complexité afin de mieux comprendre et quantifier les limitations de différents modèles pour le calcul, la communication, et la confidentialité, ainsi que pour étudier la physique quantique et les systèmes biologiques sous un nouveau regard. Ces outils incluent sur la complexité de la communication, la complexité en requêtes, la théorie de l’information et la théorie algorithmique des jeux. Voir la version anglaise pour plus d'information. Séminaire Séminaire algorithmes et complexité Permanents Nom@TéléphoneBureauFonctionPôleÉquipe Apers Simon @ 01 57 27 94 01 4026 Chargé.e de recherche - CNRS ASD algocomp Couteau Geoffroy @ 01 57 27 92 45 3041 Chargé.e de recherche - CNRS ASD algocomp De-Rougemont Michel @ 01 57 27 94 48 4041 Professeur.e - Université Paris 2 ASD algocomp Fraigniaud Pierre @ 01 57 27 92 60 4019 Directeur.rice de recherche - CNRS ASD algocomp , distribue Kerenidis Iordanis @ 01 57 27 92 63 4025 Directeur.rice de recherche - CNRS ASD algocomp Korman Amos @ 01 57 27 94 06 4028 Directeur.rice de recherche - CNRS - Currently on sabbatical at FILOFOCS ASD algocomp , distribue Laplante Sophie @ 01 57 27 94 47 4040a Professeur.e ASD algocomp Magniez Frédéric @ 01 57 27 94 02 4005 Directeur.rice de recherche - CNRS ASD algocomp Mathieu Claire @ 01 57 27 94 39 4009 Directeur.rice de recherche - CNRS ASD algocomp Perifel Sylvain @ 01 57 27 92 29 4017 Maître.sse de conférences ASV , ASD automates , algocomp Rosén Adi @ 01 57 27 94 40 4013 Directeur.rice de recherche - CNRS ASD algocomp Santha Miklos @ 4041 Directeur.rice de recherche émérite - CNRS ASD algocomp Vladu Adrian @ 01 57 27 92 45 3041 Chargé.e de recherche - CNRS ASD algocomp Non-permanents Nom@TéléphoneBureauFonctionPôleÉquipe Agarwala Aryan @ Stagiaire ASD algocomp , graphes Balthazar Bauer @ 4053 Post-Doctorant.e ASD algocomp Bermot Elie @ 3010 Doctorant.e ASD algocomp Bui Thi-Thuy-Dung @ 3014 Doctorant.e ASD algocomp Carozza Eliana @ 3014 Doctorant.e ASD algocomp Cherrat El-Amine @ 4055 Doctorant.e ASD algocomp Cornelissen Arjan @ Post-Doctorant.e ASD algocomp Csikos Monika @ 4053 Post-Doctorant.e ASD algocomp , graphes Das Avinandan @ 4055 Doctorant.e ASD algocomp , distribue Ducros Clement @ 3028 Doctorant.e ASD algocomp Egger Christoph @ 3036 Post-Doctorant.e ASD algocomp Etinski Simona @ 3010 Doctorant.e ASD algocomp Gribling Sander @ 4053 Post-Doctorant.e ASD algocomp Koch Alexander @ 3036 Post-Doctorant.e ASD algocomp Kumar Naman @ Stagiaire ASD algocomp Lechine Ulysse @ 3028 Doctorant.e ASD algocomp Leonard Arthur @ 4059 Stagiaire ASD algocomp Letao Wang @ Stagiaire ASD algocomp Luce Mael @ 3014 Doctorant.e ASD algocomp , distribue Maier Sven @ 01 57 27 94 10 4058 Post-Doctorant.e ASD algocomp Meyer Pierre @ 3010 Doctorant.e ASD algocomp Natansh Mathur @ 4056 Doctorant.e ASD algocomp Nematollahi Shamisa @ 4031 Doctorant.e ASD algocomp Pass Galina @ 4059 Visiteur.euse ASD algocomp Ramos-Vaz Daniel @ Post-Doctorant.e ASD algocomp Sellier Francois @ Doctorant.e ASD algocomp Sunny Anupa @ 4059 Doctorant.e ASD algocomp Szabo Daniel @ 4059 Doctorant.e ASD algocomp Szilagyi Eva @ 4055 Stagiaire ASD algocomp Vacus Robin @ 4055 Doctorant.e ASD algocomp , distribue