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

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 !

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:

11.12.2024
Le lundi 16 décembre 2024, SOC² organise une journée dédiée aux modèles de calcul basés sur les flots de données pour célébrer l'anniversaire du célèbre article de Gilles Kahn sur les KPN, intitulé « The semantics of a simple language for parallel programming », publié en 1974. L'objectif est d'explorer les divers domaines de recherche introduits par cet article. La journée débutera par une présentation de l'article original. Le programme ainsi que le lien d'inscription (gratuit) sont disponibles ici :

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.)

Formath
Lundi 10 février 2025, 14 heures, 3052
Jonathan Laurent (CMU) Oracular Programming

Large Language Models (LLMs) have proved surprisingly effective at solving a wide range of tasks from just a handful of examples. However, their lack of reliability limits their capacity to tackle large problems that require many steps of reasoning. In response, researchers have proposed advanced pipelines that leverage domain-specific insights to chain smaller prompts, provide intermediate feedback and improve performance through search. However, the current complexity of writing, debugging, tuning and maintaining such pipelines has put a bound on their sophistication.

We propose a new paradigm for programming with LLMs called oracular programming. In this paradigm, domain experts are invited to define high-level problem-solving strategies as nondeterministic programs. Such programs are reified into infinite search trees for LLM oracles to navigate. A separate demonstration language allows annotating choice points with examples, while keeping them grounded and synchronized as the associated program evolves.

In this talk, I will motivate and explain the key concepts of oracular programming. I will introduce Delphyne, a framework for oracular programming based on Python, discuss the associated tooling, and demonstrate Delphyne on a program verification case study. Hopefully, such a framework can foster research on intersymbolic AI and facilitate creative combinations of LLMs with symbolic provers.

Algorithmique distribuée et graphes
Mardi 11 février 2025, 15 heures, 3052
François Pirot (Saclay) Tight asymptotic bounds for odd- and pcf-colourings of graphs of bounded maximum degree

Given a graph G, a proper k-colouring of G is said to be conflict-free if, for every non-isolated vertex v ∈ V(G), there is a colour with a unique occurrence in N(v). The pcf-chromatic number of G, denoted χ_{pcf}(G), is the minimum k such that a proper conflict-free (pcf for short) k-colouring of G exists. A weakening of the notion of pcf colourings exists, where one replaces “unique occurrence” with “odd number of occurrences”; those are called odd colourings, and the related chromatic parameter is denoted χ_o(G). Recently, Caro, Petruševski, and Škrekovski formulated two conjectures on the pcf and odd chromatic numbers of graphs of maximum degree Δ ≥ 3. They conjectured that χ_{pcf}(G) ≤ Δ+1 (pcf colouring conjecture), and the weaker statement that χ_o(G) ≤ Δ+1 (odd colouring conjecture). In the first part of this presentation, I will show how a probabilistic analysis of a random colouring of G drawn uniformly from the set of proper k-colouring of G — or a well-chosen subset thereof — yields an asymptotic version of the odd colouring conjecture, namely χ_o(G) ≤ Δ+O(lnΔ) as Δ→∞. I will then discuss how to adapt this to obtain stronger results when it moreover holds that the minimum degree of G is large enough. I will finish this presentation with a sketch of the proof of an asymptotic version of the pcf colouring conjecture, namely χpcf(G)≤Δ+O(lnΔ) as Δ→∞.

Algorithmes et complexité
Mercredi 12 février 2025, 11 heures, Salle 3052
Patrick Lahr (ENS Paris Saclay) Extreme Points in Multi-Dimensional Screening

In this talk we characterize extreme points of the set of incentive-compatible mechanisms for screening problems with linear utility. Extreme points are exhaustive mechanisms, meaning their menus cannot be scaled and translated to make additional feasibility constraints binding. In problems with one-dimensional types, extreme points admit a tractable description with a tight upper bound on their menu size. In problems with multi-dimensional types, every exhaustive mechanism can be transformed into an extreme point by applying an arbitrarily small perturbation. For mechanisms with a finite menu, this perturbation displaces the menu items into general position. Generic exhaustive mechanisms are extreme points with an uncountable menu. Similar results hold in applications to delegation, veto bargaining, and monopoly problems, where we consider mechanisms that are unique maximizers for specific classes of objective functionals. The proofs involve a novel connection between menus of extreme points and indecomposable convex bodies, first studied by Gale (1954).

Sémantique
Mercredi 12 février 2025, 10 heures 45, Salle 3071
Umberto Tarantino Arrow algebras, algebraic structures for modified realizability

In this talk I will introduce arrow algebras, “algebraic” structures inducing toposes through Pitts' tripos-to-topos construction which generalise Alexandre Miquel’s implicative algebras, and I will present appropriate notions of morphisms between arrow algebras corresponding to morphisms of the associated triposes. The weakening of the axioms, from implicative algebras to arrow algebras, allows the latter to perfectly factor through the construction of realizability toposes starting from partial combinatory algebras; moreover, it allows for a particularly simple description of subtoposes of the induced toposes in terms of nuclei on the underlying arrow algebra, generalising the notion of nucleus on a frame. As an example of these properties, I will show how modified realizability can be lifted to the level of arrow algebras, recovering and extending some results known in the literature at the level of partial combinatory algebras.

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) Non encore annoncé.

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
Vincent Moreau Non encore annoncé.