Les membres de l'IRIF et les visiteurs sont priés de se conformer aux directives COVID-19 du CNRS et de l'Université de Paris.

Institut de Recherche en Informatique Fondamentale (IRIF)


L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université de Paris, qui héberge une équipe-projet Inria.

Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques.

L'IRIF regroupe près de deux cents personnes. Six de ses membres ont été lauréats de l'European Research Council (ERC), cinq sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences.

PGSM program of FSMP

IRIF will finance one or two additional Master scholarships in Foundations of Computer Science within the PGSM program of FSMP for female students who have completed a bachelor’s degree or the first year masters in one of the universities of the FSMP network. Apply online by May 8th.

Online Annual Meeting 3-5 May 2021

The Annual meeting of ANR-HOSIGRA, in collaboration with teams from India and China, will take place online May 3-6. The schedule of the talks is available here. Find abstracts and the zoom link here.

LICS 2021

Six papers coauthored by IRIF members will be presented at the prestigious conference LICS'21 this summer. Topics include game semantics, linear logic, categorical models, type theory and rewriting systems.

Blog binaire

Sylvain Perifel (IRIF) and Guillaume Lagarde (Université de Bordeaux) publish on the Blog Binaire the first article of a series about algorithmic complexity. The series aims be easy-to-understand and accessible to everyone.

(Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.)

Lundi 10 mai 2021, 11 heures, BBB link
Laurent Doyen (LMF — ENS Saclay) Observation and Distinction. Representing Information in Infinite Games

We compare two approaches for modelling imperfect information in infinite games by using finite-state automata. The first, more standard approach views information as the result of an observation process driven by a sequential Mealy machine. In contrast, the second approach features indistinguishability relations described by synchronous two-tape automata.

The indistinguishability-relation model turns out to be strictly more expressive than the one based on observations. We present a characterisation of the indistinguishability relations that admit a representation as a finite-state observation function. We show that the characterisation is decidable, and give a procedure to construct a corresponding Mealy machine whenever one exists.

The talk is based on joint work with Dietmar Berwanger.

Algorithmique distribuée et graphes
Mardi 11 mai 2021, 14 heures, ZOOM
Bérénice Delcroix-Oger Parking trees

In 1980, Edelman defined a poset on objects called noncrossing 2-partitions, made of a partition and a noncrossing partition, with a bijection linking parts of the same size in both partitions. Studying this poset, he proved that the number of noncrossing 2-partitions is given by (n+1)^{n-1}. This is also the number of classical combinatorial objects called parking functions. After introducing noncrossing partitions, noncrossing 2-partitions and parking functions, we will draw the link between parking functions and noncrossing 2-partitions, describing Edelman's poset in terms of parking functions. Afterwards, we will (recall and) use the notion of species introduced in the early 1980s by Joyal to describe the action of the symmetric group on a poset on parking trees.

This is a joint work with Matthieu Josuat-Vergès and Lucas Randazzo.

Soutenances de thèses
Mardi 11 mai 2021, 15 heures, Online
Yixin Shen (IRIF) Classical and quantum cryptanalysis for Euclidean lattices and subset sum

Post-quantum cryptography is a branch of cryptography that aims at designing non-quantum (i.e. classical) cryptographic systems, which are protected against an adversary possessing a quantum computer. In this thesis, we focus on the study of two fundamental problems for post-quantum cryptography: the shortest vector problem (SVP) and the random subset sum problem. We propose several classical/quantum algorithms that improve the state of the art.

One world numeration seminar
Mardi 11 mai 2021, 14 heures 30, Online
Giulio Tiozzo (University of Toronto) The bifurcation locus for numbers of bounded type

We define a family B(t) of compact subsets of the unit interval which provides a filtration of the set of numbers whose continued fraction expansion has bounded digits. This generalizes to a continuous family the well-known sets of numbers whose continued fraction expansion is bounded above by a fixed integer.

We study how the set B(t) changes as the parameter t ranges in [0,1], and describe precisely the bifurcations that occur as the parameters change. Further, we discuss continuity properties of the Hausdorff dimension of B(t) and its regularity.

Finally, we establish a precise correspondence between these bifurcations and the bifurcations for the classical family of real quadratic polynomials.

Joint with C. Carminati.

Algorithmes et complexité
Mercredi 12 mai 2021, 10 heures, Collège de France
Frédéric Magniez - Miklos Santha (IRIF - CNRS, CQT) Transformée de Fourier quantique I

Quatrième cours de Frédéric Magniez au Collège de France sur les Algorithmes quantiques (à 10h), suivi d'un exposé de Miklos Santha sur « Le problème du sous-groupe caché » (à 11h30). Informations supplémentaires : https://www.college-de-france.fr/site/frederic-magniez/course-2021-05-12-10h00.htm

Preuves, programmes et systèmes
Jeudi 13 mai 2021, 16 heures, Online at link (any password works)
Carlo Angiuli (Carnegie Mellon University) Internalizing Representation Independence with Univalence