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 deux équipes-projets 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) et deux sont membres de l'Academia Europæa.


Sylvain Périfel from IRIF, together with Damiano Mazza and Thomas Seiller, organize the Caleidoscope Research School in Computational Complexity, to be held in Paris, 15-19 June 2020.

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 by May 8th.

The ANR PPS kick-off meeting will take place from Feb 26 to Feb 28, 2020 at IRIF (Paris) and will be joined with the 3rd edition of the PIHOC workshop series initiated by Ugo Dal Lago in 2018 and with Dal Lago's DIAPASoN ERC project kick-off meeting. Register by Jan 31: registration is free but mandatory.

The ASD day of « Algorithms and discrete structures » pole will take place in room 3052 on January 27th.

JFLA 2020

Yann Régis-Gianas (IRIF) is the vice-president of the “Journées Francophones des Langages Applicatifs” that will take place at Gruissan from the 29th of January to the 1st of February.

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

Lundi 17 février 2020, 11 heures, Salle 1007
Corto Mascle (ENS de Cachan) On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words

Unambiguous automata are a popular compromise between non-deterministic and deterministic automata in terms of succinctness and complexity. A word is called a killing word for an automaton if there is no path labelled by it in this automaton. Here we will discuss the problem of computing a short killing word for an unambiguous automaton, as well as possible extensions. Unambiguous automata are closely related to codes, and this problem can be viewed as a particular instance of Restivo's conjecture, a longstanding problem in the theory of codes. It can also be interpreted as a restricted version of the matrix mortality problem. This is a joint work with Stefan Kiefer, published at STACS 2019.

Algorithmes et complexité
Mardi 18 février 2020, 10 heures, Salle 3052
Alantha Newman (Université Grenoble Alpes) Approximation algorithms based on LP and SDP rounding (Lecture 3/4)

SDP Rounding (basic concepts such as problem formulations, normal distribution, random hyperplane rounding).

Additional information:

Combinatoire énumérative et analytique
Jeudi 20 février 2020, 14 heures, Salle 1007
Viviane Pons (Université Paris-sud) Involution “Montée - Contacts” sur les intervalles de Tamari

Nous présentons une involution sur les intervalles de Tamari qui échange deux séries de statistiques : les “montées” et les “contacts”. Cette involution fait intervenir de nombreux objets combinatoires : chemins de Dyck, arbres, intervalles-posets.

Algorithmes et complexité
Jeudi 20 février 2020, 10 heures, Salle 3052
Alantha Newman (Université Grenoble Alpes) Approximation algorithms based on LP and SDP rounding (Lecture 4/4)

Applications: Max-k-cut, graph coloring, theta function and perfect graphs, unique games.

Additional information:

Vendredi 21 février 2020, 14 heures 30, Salle 3052
Luc Dartois (LACL) Reversible Transducers

Transducers extend automata by adding outputs to the transition, thus computing functions over words instead of recognizing languages. Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms for composing two-way transducers are rather involved and cause a double exponential blow-up in the size of the input machines. This contrasts with the rather direct and polynomial construction for composing one-way machines. In this talk, I will present the class of reversible transducers, which are machines that are both deterministic and co-deterministic. This class enjoys polynomial composition complexity, even in the two-way case. Although this class is not very expressive in the one-way scenario, I will show that any two-way transducer can be made reversible through a single exponential blow-up. As a consequence, the composition of two-way transducers can be done with a single exponential blow-up in the number of states, enhancing the best known algorithm from the 60s.

Maintenu malgré les vacances, car présence attendue d'une dizaine de personnes (après sondage)

Lundi 24 février 2020, 11 heures, Salle 1007
James Worrell (University of Oxford) Termination of linear constraint loops

We consider the problem of deciding termination of linear constraint loops, that is, single-path loops in which the loop body consists of a (possibly non-deterministic) assignment, specified a conjunction of linear constraints. We present several versions of this problem, according to the syntactic form of the loop and the numerical domain of the program variables. We sketch some decidability results and point out open problems.