Institut de Recherche en Informatique Fondamentale (IRIF)


Université Paris Cité

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, 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.

Accepted paper ICALP 2022

Gaëtan Douéneau-Tabot (IRIF, DGA) will present at ICALP 2022 his paper Hiding pebbles when the output alphabet is unary. Pebble transducers are simple programs which compute functions over finite words. This paper studies subclass membership problems for the functions computed by pebble transducers whose outputs are unary. Its results can be understood as program optimization techniques.

Accepted paper ICALP 2022

Antonio Casares (IRIF), Thomas Colcombet (IRIF) and Karoliina Lehtinen (Aix-Marseille University) will present at ICALP 2022 their paper studying the link between good-for-games Rabin automata and memory structures for infinite duration games over graphs. They also establish that these automata can be exponentially more succinct than equivalent deterministic ones.

ICALP 2022 Accepted papers

3 papers coauthored by IRIF members will be presented at ICALP 2022, July 4-8 in Paris, campus Grands Moulins of Université Paris Cité. Complete list of accepted papers here.

Program of the evening 75 years

On May 9th at 6pm will be held the festive evening of 75 years of computer science, from its foundations to its impact on society. This event is organized by LIP6 with the help from IRIF. Program and details of the evening here.

Interview ICALP 2022 - FSMP

Thomas Colcombet, Geoffroy Couteau et Sylvain Schmitz members of IRIF and part of ICALP 2022 organizing committee were interviewed by FSMP (Fondation Sciences Mathématiques de Paris), one of the co-organizers of the conference. Learn more about the goals of the conference and what makes it special this year (interview in French only).

Cocktail de célébration des 75 d’informatique en France

On May 9th, 2022, LIP6 and IRIF are organizing a cocktail celebrating the 75th anniversary of computer science in France. A panel of experts will explore the discipline from its foundations to its impacts on society.

Teaching Assistant positions

[Update on the calendar] Four Teaching Assistants positions plus three other potential teaching assistant positions that may become available upon contest within UFR d’Informatique of Université Paris Cité fort he academic year 2022-2023. To learn more and to apply, visit: Deadline to apply, May 4th 2022 (4:00 pm Paris time).

Portrait Mohammed Foughali

IRIF has the great pleasure to welcome a new Associate Professor: Mohammed Foughali, an expert in formal verification and robotics. Learn more about him and his work here.

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

Lundi 30 mai 2022, 11 heures, 3052 and Zoom link
Miquel Oliu-Barton (Université Paris-Dauphine and Bruegel) New algorithms for solving zero-sum stochastic games

Zero-sum stochastic games, henceforth stochastic games, are a classical model in game theory in which two opponents interact and the environment changes in response to the players’ behavior. The central solution concepts for these games are the discounted values and the value, which represent what playing the game is worth to the players for different levels of impatience. In the present manuscript, we provide algorithms for computing exact expressions for the discounted values and for the value, which are polynomial in the number of pure stationary strategies of the players. This result considerably improves all the existing algorithms.

One world numeration seminar
Mardi 31 mai 2022, 14 heures 30, Online
Verónica Becher (Universidad de Buenos Aires & CONICET Argentina) Poisson generic real numbers

Years ago Zeev Rudnick defined the Poisson generic real numbers as those where the number of occurrences of the long strings in the initial segments of their fractional expansions in some base have the Poisson distribution. Yuval Peres and Benjamin Weiss proved that almost all real numbers, with respect to Lebesgue measure, are Poisson generic. They also showed that Poisson genericity implies Borel normality but the two notions do not coincide, witnessed by the famous Champernowne constant. We recently showed that there are computable Poisson generic real numbers and that all Martin-Löf real numbers are Poisson generic.

This is joint work Nicolás Álvarez and Martín Mereb.

Combinatoire énumérative et analytique
Jeudi 2 juin 2022, 11 heures, IHP
Seminaire Flajolet Seminaire Flajolet

Preuves, programmes et systèmes
Jeudi 2 juin 2022, 10 heures 30, Salle 3052 & online
Cezary Kaliszyk (University of Innsbruck) Non encore annoncé.

Séminaire des doctorants
Jeudi 2 juin 2022, 16 heures, Salle 3052
Avinandan Das Correlation clustering using sparse-dense decomposition

Analyse et conception de systèmes
Vendredi 3 juin 2022, 10 heures 30, Salle 1007
Yaëlle Vincont Non encore annoncé.

Graph Transformation Theory and Applications
Vendredi 3 juin 2022, 15 heures, online
Frank Drewes, Berthold Hoffmann, Mark Minas (Department of Computing Science, Umeå University, Sweden, Department of Mathematics and Informatics, University of Bremen, Germany, Institute for Software Technology, Computer Science Department, Universität der Bundeswehr München , Germany) Contextual Hyperedge Replacement Grammars: Languages – Parsing – Grappa

Graph transformation allows to extend formal language theory to the generation of graph languages. This has applications in areas such as model-driven software engineering, natural language processing, and shape analysis of programs.

We start from the well-established theory of context-free grammars based on hyperedge replacement (HR) and introduces a modest extension, contextual hyperedge replacement (CHR), in order to extend their generative power. We discuss the generative power and other properties of CHR, and relate them to HR.

Then we consider parsing for CHR grammars. As for HR, parsing is NP-complete in general, so that efficient parsing algorithms can only be achieved for subclasses. We have devised two algorithms, called predictive top-down (PTD) and predictive shift-reduce (PSR), which are inspired by the well-known LL(k) and LR(k) parsing for strings, and are usually linear, at most quadratic. We illustrate the ideas of these algorithms by graph transformation rules.

Finally we demonstrate Mark Minas' graph parser generator Grappa, which implements not only PTD and PSR parsing, including the needed analysis tools, but also generalized PSR, where parallel parsing allows to cope with ambiguous grammars. Measurements of generated parsers validate our theoretical findings regarding complexity.

Zoom meeting registration link

YouTube live stream

Algorithmes et complexité
Mardi 7 juin 2022, 11 heures, Salle 3052
Francesco Mazzoncini (Télécom Paris) Hybrid Quantum Cryptography from One-way Quantum Communication Complexity Separation

We introduce an explicit construction for a key distribution protocol in the Quantum Computational Timelock (QCT) security model, where one assumes that computationally secure encryption may only be broken after a time much longer than the coherence time of available quantum memories. Taking advantage of the QCT assumptions, we build a key distribution protocol called HM-QCT from the Hidden Matching problem for which there exists an exponential gap in one-way communication complexity between classical and quantum strategies. We establish that the security of HM-QCT against arbitrary attacks can be reduced to the difficulty of solving the underlying distributed problem with classical information, while legitimate users can use quantum communication. This leads to a HM-QCT key distribution scheme over n bosonic modes that can be secure with up to O(sqrt(n)/log(n)) input photons per channel use, boosting key rates by several orders of magnitude compared to QKD and allowing to operate with a non-trusted receiver.

Algorithmes et complexité
Mardi 7 juin 2022, 16 heures, Salle 3052
Srikanth Srinivasan (IIT Bombay) Non encore annoncé.

One world numeration seminar
Mardi 7 juin 2022, 14 heures 30, Online
Sophie Morier-Genoud (Université Reims Champagne Ardenne) q-analogues of real numbers

Classical sequences of numbers often lead to interesting q-analogues. The most popular among them are certainly the q-integers and the q-binomial coefficients which both appear in various areas of mathematics and physics. With Valentin Ovsienko we recently suggested a notion of q-rationals based on combinatorial properties and continued fraction expansions. The definition of q-rationals naturally extends the one of q-integers and leads to a ratio of polynomials with positive integer coefficients. I will explain the construction and give the main properties. In particular I will briefly mention connections with the combinatorics of posets, cluster algebras, Jones polynomials, homological algebra. Finally I will also present further developments of the theory, leading to the notion of q-irrationals and q-unimodular matrices.