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.

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
Leo Stefanesco (Équipes “Preuves et Programmes” et “Algèbre et Calcul”) “A concise introduction to logical relations” followed by “A Logical Relation for Monadic Encapsulation of State”

1st part (E for Everyone): A concise introduction to logical relations

Logical relations are a powerful technique to prove properties about programs. In particular, for proving that two programs are contextually equivalent.

In this talk, we will see that, in System F (aka the polymorphic lambda calculus), the only programs of type $forall a, a \rightarrow a$ is the identity.

I will also sketch how to extend logical relations to realistic languages such as ML.

2nd part (POPL talk rehearsal):

A Logical Relation for Monadic Encapsulation of State

We present a logical relations model of a higher-order functional programming language with impredicative polymorphism, recursive types, and a Haskell-style ST monad type with runST. We use our logical relations model to show that runST provides proper encapsulation of state, by showing that effectful computations encapsulated by runST are heap independent. Furthermore, we show that contextual refinements and equivalences that are expected to hold for pure computations do indeed hold in the presence of runST. This is the first time such relational results have been proven for a language with monadic encapsulation of state. We have formalized all the technical development and results in Coq.

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.