L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris-Diderot, qui héberge deux équipes-projets INRIA.

Les objectifs scientifiques de l'IRIF se situent au cœur de l'informatique, se focalisant sur la conception, l'analyse, la preuve et la vérification d'algorithmes et de programmes, appuyé sur des recherches fondamentales en combinatoire, théorie des graphes, logique, théorie des automates, etc.

L'IRIF regroupe près de 170 personnes. Six de ses membres ont été lauréats de l'European Research Council (ERC), et deux sont membres de l'Institut Universitaire de France (IUF).


Amina Doumane

29.11.2017
Amina Doumane was awarded the Gilles Kahn prize for her PhD thesis entitled « On the infinitary proof theory of logics with fixed points » supervised by Alexis Saurin, David Baelde and Pierre-Louis Curien.

Wenjie Fang

29.11.2017
Wenjie Fang was awarded the Honorable Mention of the Gilles Kahn prize for his PhD thesis entitled « Aspects énumératifs et bijectifs des cartes combinatoires : généralisation, unification et application » and supervised by Guillaume Chapuy and Mireille Bousquet-Mélou.

Maurice Nivat

27.11.2017
Scientific Day in memory of Maurice Nivat, professor at Paris Diderot University and a pionneer of thoeretical computer science in France and in the world, who passed away on September the 21st, 2017.

15.11.2017
IRIF is happy to host and organize the 59th IEEE Symposium on Foundations of Computer Science (FOCS 2018), at Maison de la Chimie, Paris, October 07-09, 2018.

15.11.2017
2-day workshop on December 7-8: Closing workshop of ANR project on Restricted Data Access Models and 1st IRIF-IQC Workshop on Quantum Information Processing (CNRS bilateral collaboration).

06.10.2017
Guillaume Lagarde and Sylvain Perifel have solved a 20-year old conjecture related to Lempel-Ziv. This will be presented at the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

01.09.2017
IRIF has the great pleasure to welcome a new assistant professor: Bérénice Delcroix-Oger, an expert in combinatorics and computational algebra.

15.06.2017
Victor Lanvin is awarded the first prize for the ACM Student Research Competition Grand Finals, undergraduate category. The prize will be presented on June the 24th at the Turing Award Cerimony in San Francisco.

Séminaire des doctorants
mercredi 13 décembre 2017, 11h00, Salle 3052
Simon Halfon (ENS Cachan) Well Quasi-Orders and Extreme Stratospheric-Complexity-Classes of Death — Beaux pré-ordres et classes de complexité stratosphériques de la mort

It is widely known how to prove the termination of an algorithm using well-founded orderings. It is however usually believed that no complexity upper bound can be derived from these termination proof, often seen as non-constructive. In this talk, I will present some ideas to infer upper bounds from such termination proofs. I will try to give you a taste of the complicated combinatorics behind, that results in surprisingly high complexities. Oxygen bottles and pressure suits required, we are going beyond Elementary.

No special knowledge is required to follow the talk.

Nous savons tous qu’il est très pratique pour prouver la terminaison d’un algorithme d’utiliser des ordres bien fondés. Cependant, il est commun de penser que cette technique ne donne aucune information sur la complexité de l’algorithme, car la preuve est non constructive. Dans cet exposé, je présenterai quelques idées pour extraire une borne supérieur de complexité d’une telle preuve de terminaison. J’essaierai de vous donner une idée de la combinatoire compliquée que cela engendre, et qui résulte en des complexité très élevée. Bouteilles d’oxygène et combinaisons pressurisées obligatoire, on s’envole au delà de l’Élémentaire.

Aucune connaissance spécifique n'est nécessaire pour suivre l'exposé.

Preuves, programmes et systèmes
jeudi 14 décembre 2017, 10h30, ENS Lyon
Séminaire Chocola () ENS Lyon

Preuves, programmes et systèmes
jeudi 14 décembre 2017, 10h30, Salle 3052
Juliusz Chroboczek (IRIF, Université Paris Diderot) Homenet, l'IETF, et le processus de normalisation

Depuis plusieurs années, je participe au groupe de travail Homenet de l'IETF, l'organisme qui définit les normes qui régissent l'Internet. Dans cet exposé, sur l'exemple de Homenet et de mes aventures à l'IETF, j'essaierai de donner une idée de ce qu'est le processus de normalisation, pourquoi il est important pour l'Informatique et pour l'Internet.

Cet exposé est une version étendue et légèrement censurée de l'exposé que j'ai donné aux Journées PPS le 12 octobre 2017.

Algorithmes et complexité
jeudi 14 décembre 2017, 14h30, Salle 1016
Emanuele Natale (Max Planck Institute for Informatics) Computing through Dynamics: Principles for Distributed Coordination

We present analytical results regarding some simple randomized protocols, called dynamics, for solving fundamental distributed consensus problems, together with examples on how to use them to build lightweight algorithms for other important distributed problems. More specifically, we provide an overview of the theory regarding several dynamics such as the 3 Majority, the Averaging and the Undecided-State ones, and we show how to use them to solve plurality consensus, distributed clustering, clock synchronization and information spreading. Motivated by applications to systems whose complexity is in-between biological and human-made ones, we focus mainly on unstructured and random interaction models, and we also deal with scenarios in which the communication is affected by noise or when a self-stabilizing protocol is required.

Algorithmes et complexité
mardi 19 décembre 2017, 10h00, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot
Claire Mathieu - Bruno Salvy (DI ENS, IRIF - INRIA) On Analytic Combinatorics

Fourth lecture from Claire Mathieu at Collège de France on Algorithms (at 10am), followed by a talk from Bruno Salvy on Analytic Combinatorics (at 11am).

Additional information: http://www.college-de-france.fr/site/claire-mathieu/course-2017-12-19-10h00.htm

Théorie des types et réalisabilité
mercredi 20 décembre 2017, 14h00, Salle 1007
Ludovic Patey () Sur les degrés de Weihrauch

Séminaire des doctorants
mercredi 20 décembre 2017, 11h00, Salle 3052
Léo Stefanesco (Équipes “Preuves et Programmes” et “Algèbre et Calcul”) TBA