IRIF is a research laboratory of CNRS and Université Paris-Diderot, hosting two INRIA project-teams.

The scientific objectives of IRIF are at the core of computer science, focusing on conception, analysis, proof and verification of algorithms and programs, built upon fundamental research activities on combinatorics, graph theory, logics, automata theory, etc.

IRIF hosts around 170 people. Six of its members have been distinguished by the European Research Council (ERC), and two of them are members of the Institut Universitaire de France (IUF).

Amina Doumane

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

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

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.

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.

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).

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).

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

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.

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:

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

Combinatoire énumérative et analytique
jeudi 21 décembre 2017, 11h45, Salle 1007
Pierre-Loïc Méliot (Université Paris-sud) Fluctuations des mesures centrales sur les partitions

On s’intéresse aux fluctuations en grande dimension de modèles de partitions aléatoires introduits dans les années 80 par Kerov et Vershik. On montrera que pour tout modèle de ce type, une observable générique des partitions aléatoires est asymptotiquement gaussienne, et que l’on peut compléter ce résultat par une estimée de la vitesse de convergence et par une inégalité de concentration. La structure qui émerge pour ces mesures centrales sur les partitions est celle d’espace de modules mod-gaussien ; c’est une structure que l’on retrouve également pour les modèles de graphons et de permutons.