Institut de Recherche en Informatique Fondamentale (IRIF)

CNRS

Université Paris Cité

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, et 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. Sept de ses membres ont été lauréats de l'European Research Council (ERC), trois 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.

Suivez nous sur LinkedIn, Bluesky et Mastodon :

LinkedIn  Bluesky  Mastodon

stoc_2025.jpg

10.2.2025
Félicitations à Adrian Vladu, membre de l'IRIF, dont l'article a été accepté à STOC 2025, une conférence ACM :

cnrs_editions_lecalculadecouvert.jpg

10.2.2025
CNRS EDITIONS a publié un nouvel ouvrage sur l'histoire du calcul, intitulé 𝐿𝑒 𝑐𝑎𝑙𝑐𝑢𝑙 𝑎̀ 𝑑𝑒́𝑐𝑜𝑢𝑣𝑒𝑟𝑡. Plusieurs chercheurs actuels et anciens de l'IRIF ont contribué à la rédaction de ce livre en rédigeant des chapitres :
◻️ Partie 4 : ▪️ Chapitre 1 - 𝑳'𝒂𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎𝒆 : 𝒗𝒆𝒓𝒔 𝒍𝒂 𝒓𝒆́𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒄𝒐𝒏𝒄𝒓𝒆̀𝒕𝒆 𝒅𝒆 𝒑𝒓𝒐𝒃𝒍𝒆̀𝒎𝒆𝒔 - Claire Mathieu
▪️ Chapitre 2 - 𝑳𝒂 𝒄𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒆́ 𝒂𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎𝒊𝒒𝒖𝒆 - Sylvain Perifel
◻️ Partie 9 : ▪️ Chapitre 1 - 𝑳𝒆𝒔 𝒇𝒐𝒏𝒅𝒆𝒎𝒆𝒏𝒕𝒔 𝒅𝒖 𝒄𝒂𝒍𝒄𝒖𝒍 𝒒𝒖𝒂𝒏𝒕𝒊𝒒𝒖𝒆 - Frédéric Magniez

22.1.2025
Le troisième Paris ACTS, aura lieu à l'IRIF, le mercredi 29 janvier. P-ACTS est une série de séminaires centrés sur les connexions entre la théorie des automates et la théorie de la concurence, partagés entre l'EPITA, l'IRIF et le LIX. Les deux intervenants seront Laetitia Laversa et Glynn Winskel. Les conférences seront également diffusées sur Zoom. Pour les résumés et plus d'informations sur le séminaire, voir cette page:

30.1.2025
Félicitations à Esaïe Bauer et Alexis Saurin dont le papier à été accepté pour la conférence FoSSaCS 2025 !

30.1.2025
Trois articles de membres de l'IRIF ont été acceptés à ESOP 2025. Félicitations à Giovanni Bernardi, Thomas Ehrhard, Claudia Faggian et Giulia Manara !

6.1.2025
L'IRIF vous souhaite une excellente année, riche en découvertes scientifiques, en succès académiques et en épanouissement personnel !

7.1.2025
Nous sommes heureux d'accueillir notre nouvelle responsable financière et comptable, Chafia Dordoigne. Vous pouvez la rencontrer dans le bureau 4002.


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

Preuves, programmes et systèmes
Jeudi 13 février 2025, 10 heures 30, Salle 3052 & online (Zoom link)
Léo Andrès (OCamlPro, Laboratoire de Méthodes Formelles) Owi, a cross-language symbolic execution engine for bug-finding and solver-aided programming

In this talk, we will introduce Owi, a symbolic execution engine for WebAssembly (Wasm). We will begin by detailing how we extended a concrete Wasm interpreter to support symbolic execution. Next, we will show how we used OCaml 5 to parallelize the exploration, allowing multi-core execution. Since Wasm is a compilation target, we will demonstrate how Owi can be applied to perform symbolic execution of programs written in C, C++ and Rust by compiling them to Wasm. Finally, we will give examples of practical applications of symbolic execution, such as bug finding or solver-aided programming.

Séminaire des membres non-permanents
Jeudi 13 février 2025, 16 heures, Salle 3052
Adrienne Lancelot Non Permanent General Assembly

The aim of this assembly is to gather your thoughts, (dis)likes and fears about office space at IRIF.

The direction of the lab is currently indicating that we will soon struggle with too many recruitments and not enough desks. This will surely impact non permanents (recruitments are mostly Post Docs and PhD students). I will take part in the discussions about how to deal with this issue, and while I already have some opinions, I would like to hear yours and make them known. As an example of possible discussion, if we were to have more non permanents per office, it would likely be critical to offer specific rooms for video calls.

Automates
Vendredi 14 février 2025, 14 heures, Salle 3052
Sylvain Lombardy (LaBRI) On Two-way Q-Automata

Joint work with Louis-Marie DANDO

Two-way automata are natural models of computation. Nevertheless, it was proven in 1959 (both by Jefferson, and by Rabin and Scott) that they are not more powerful than one-way automata.

In the framework of weighted automata, things are more complicated, thus interesting. We focus in this talk on automata where weights are rational numbers. We present a hierarchy of Q-automata: rotating, sweeping and 2-way automata. We show a natural extension of the Kleene-Schützenberger theorem between rotating Q-automata and Hadamard series which are extensions of rational series. Finally, we prove that 2-way Q-automata are not more powerful than rotating Q-automata.

Vérification
Lundi 17 février 2025, 11 heures, 3052 and Zoom link
Niklas Kochdumper (IRIF) Robust Identification of Hybrid Automata from Noisy Data

In recent years, many different methods for identifying hybrid automata from data have been proposed. However, most of these methods consider clean simulator data, and consequently do not perform well for noisy data measured from real systems. We address this shortcoming with a new approach for the identification of hybrid automata that is specifically designed to be robust to noise. In particular, we propose a new high-level strategy consisting of the following three steps: clustering based on the dynamics identified from a local dataset, state space partitioning using decision trees, and conversion of the decision tree to a hybrid automaton. In addition, we introduce several new concepts for the realization of the single steps. For example, we propose an automated regularization of the dynamic models used for clustering via rank adaption, as well as a new variant of the Gini impurity index for decision tree learning, tailored toward hybrid systems where different dynamics can be active within the same state space region. As our experiments on 19 challenging benchmarks with different characteristics demonstrate, in addition to being robust to both process and measurement noise, our approach avoids the need for extensive hyper-parameter tuning and also performs well for clean data without noise.

Algorithmique distribuée et graphes
Mardi 18 février 2025, 15 heures, 3052
Bernadette Charron-Bost (Ens Paris) Know your audience (Communication models and function computability in anonymous networks)

In this talk, we present exact characterizations of the functions that are computable in anonymous networks with varying assumptions in the degree of awareness or control that agents have over their outneighbors. First, we characterize the computable functions in the “blind broadcast” model, i.e., when agents have no information on their outgoing neighborhoods. Then we enrich this communication model with either output port awareness, bidirectional channels, or outdegree awareness: In each case, we prove that a function can be computed if and only it is frequency-based, namely, its value only depends on the frequencies of the different input values. This characterization holds for both exact and approximate computability. If one or several nodes are distinguished as leaders, or if the cardinality of the network is known, then under any of the above three assumptions it becomes possible to compute any symmetric function.

Sémantique
Mardi 18 février 2025, 15 heures, Salle 3071
Quentin Aristote Monotone weak distributive laws over the lifted powerset monad in categories of algebras

Noticing the similarity between the monotone weak distributive laws combining two layers of non-determinism in sets and in compact Hausdorff spaces, we study whether the latter law can be obtained automatically as a weak lifting of the former. This holds partially, but does not generalize to other categories of algebras: we then characterize when exactly monotone weak distributive laws over powerset monads in categories of algebras exist, exhibiting a law combining probabilities and non-determinism in compact Hausdorff spaces and showing on the other hand that such laws do not exist in a lot of other cases.

One world numeration seminar
Mardi 18 février 2025, 14 heures, Online
Neil Macvicar (Queen's University) Intersecting Cantor sets generated by Complex Radix Expansions

Consider the classical middle third Cantor set. This is a self-similar set containing all the numbers in the unit interval which have a ternary expansion that avoids the digit 1. We can ask when the intersection of the Cantor set with a translate of itself is also self-similar. Sufficient and necessary conditions were given by Deng, He, and Wen in 2008. This question has also been generalized to classes of subsets of the unit interval. I plan to discuss how existing ideas can be used to address the question for certain self-similar sets with dimension greater than one. These ideas will be illustrated using a class of self-similar sets in the plane that can be realized as radix expansions in base $-n+i$ where $n$ is a positive integer. I will also discuss a property of the fractal dimensions of these kinds of intersections.

Séminaire des membres non-permanents
Jeudi 20 février 2025, 16 heures, Salle 3052
Miriam Marzaioli A Crèche Introduction to Cohen's Forcing

In 1963, Paul Cohen discovered the forcing method and definitively answered the first of Hilbert's 23 problems by using this technique to prove the independence of the Continuum Hypothesis from the ZFC axioms. Since then, forcing has become the primary tool in set theory for establishing independence and consistency results. In this talk, we will present the key ingredients and ideas necessary to understand Cohen's model of ZFC + ¬CH. In particular, we will explore Cohen's forcing via the boolean-valued models approach.

Automates
Vendredi 21 février 2025, 14 heures, Salle 3052
Andrew Ryzhikov (University of Warsaw) How combinatorics stands in the way of matrix reachability (and what we can do about that)

Combinatorial automata theory can be seen as studying reachability in transformation semigroups. An interesting way of generalising this setting is by lifting it up to reachability in finite semigroups of rational matrices. Here, besides finite automata theory, other areas come into play, for example weighted automata, algebraic number theory, and multilinear algebra. I will explain several nice questions (such as mortality and minimum rank) that transfer from transformation semigroups to finite matrix semigroups. I will also explain the lack of mathematical structure that is brought by certain PSPACE-complete transformation semigroup problems.

Algorithmique distribuée et graphes
Mardi 25 février 2025, 15 heures, 3052
Narges Tavassoli (CRIStAL, Université de Lille) Non encore annoncé.