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.

Conférence Maths en Mouvement

L'édition 2021 de Mathématiques en mouvement, organisée par la FSMP, aura lieu le mercredi 19 mai de 14h à 17h15 en visioconférence. Elle aura pour thème Maths et sport.

ICALP'21-Accepted papers

Six papers coauthored by IRIF members will be presented at the prestigious conference ICALP’21 this summer.

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.

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.

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.

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

One world numeration seminar
Mardi 18 mai 2021, 14 heures 30, Online
Joseph Vandehey (University of Texas at Tyler) Solved and unsolved problems in normal numbers

We will survey a variety of problems on normal numbers, some old, some new, some solved, and some unsolved, in the hope of spurring some new directions of study. Topics will include constructions of normal numbers, normality in two different systems simultaneously, normality seen through the lens of informational or logical complexity, and more.

Algorithmes et complexité
Mercredi 19 mai 2021, 10 heures, Collège de France
Frédéric Magniez - Stacey Jeffery (IRIF - CWI) Optimisation quantique

Cinquième cours de Frédéric Magniez au Collège de France sur les Algorithmes quantiques (à 10h), suivi d'un exposé de Stacey Jeffery sur « A Unified Framework for Quantum Walk Search » (à 11h30). Informations supplémentaires : https://www.college-de-france.fr/site/frederic-magniez/course-2021-05-19-10h00.htm

Preuves, programmes et systèmes
Jeudi 20 mai 2021, 10 heures, Online
Valeria Vignudelli (École normale supérieure de Lyon) Non encore annoncé.

Vendredi 21 mai 2021, 14 heures 30, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl
Enrico Formenti Non encore annoncé.

Graph Transformation Theory and Applications
Vendredi 21 mai 2021, 15 heures, online
Andrea Corradini (Computer Science Department, University of Pisa, Italy) From Petri Nets to Graph Rewriting Systems: aspects of truly concurrent semantics

Graph rewriting systems are naturally endowed with a notion of parallelism due to the locality of the effect of rules. These aspects have been studied in the classical theory from an interleaving perspective, based on sequential independence, shift equivalence and related notions. In the last three decades the theory has been enriched with notions, constructions and results which provide a direct account of causality and non-determinism in graph derivations, borrowed from (and extending) the theory of Petri Nets. In the talk I will present a personal overview of the development of this theory starting from the basic structural relation between nets and graph rewriting systems, and I will survey some more recent developments.

Zoom registration

YouTube live stream

One world numeration seminar
Mardi 25 mai 2021, 14 heures 30, Online
Charles Fougeron (IRIF) Dynamics of simplicial systems and multidimensional continued fraction algorithms

Motivated by the richness of the Gauss algorithm which allows to efficiently compute the best approximations of a real number by rationals, many mathematicians have suggested generalisations to study Diophantine approximations of vectors in higher dimensions. Examples include Poincaré's algorithm introduced at the end of the 19th century or those of Brun and Selmer in the middle of the 20th century. Since the beginning of the 90's to the present day, there has been many works studying the convergence and dynamics of these multidimensional continued fraction algorithms. In particular, Schweiger and Broise have shown that the approximation sequence built using Selmer and Brun algorithms converge to the right vector with an extra ergodic property. On the other hand, Nogueira demonstrated that the algorithm proposed by Poincaré almost never converges.

Starting from the classical case of Farey's algorithm, which is an “additive” version of Gauss's algorithm, I will present a combinatorial point of view on these algorithms which allows to us to use a random walk approach. In this model, taking a random vector for the Lebesgue measure will correspond to following a random walk with memory in a labelled graph called symplicial system. The laws of probability for this random walk are elementary and we can thus develop probabilistic techniques to study their generic dynamical behaviour. This will lead us to describe a purely graph theoretic criterion to check the convergence of a continued fraction algorithm.