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

podcast_geoffroycouteau.jpg

14.3.2025
Le troisième épisode du podcast “Qu'est ce que tu cherches ?” du CNRS a invité Geoffroy Couteau pour parler de son sujet de recherche : la protection des données privées, les calculs sécurisés, les protocoles sécurisés. Vous pourrez également découvrir sa journée type, le moment où il fait le plus de sciences (et non, ce n'est pas forcément pendant la journée !), les stéréotypes liés à son domaine. (Ré)Écoutez cet épisode :

aaai_2025.jpg

10.3.2025
Félicitations à Florian Horn, co-auteur de Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives, papier récompensé par le prix “Outstanding Paper Awards” à AAAI 2025.


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

Programmation
Lundi 19 mai 2025, 10 heures, 3071
Marco Peressotti (SDU) Choreographic programming: from theory to practice

Choreographies are coordination plans for concurrent and distributed systems. They define the roles of the involved participants and how they are supposed to work together. In the paradigm of choreographic programming, choreographies are programs that can be compiled into executable, correct-by-construction, decentralised implementations. This talk introduces the paradigm of choreographic programming, its key principles and benefits, and how it has recently matured from a theory based on process algebra to a full-fledged programming paradigm that has been applied to popular languages like Java, Haskell, and Rust to write distributed software more concisely and correctly.

Formath
Lundi 19 mai 2025, 14 heures, 3052 et en visio
François Lamarche La topologie algébrique et la géométrie peuvent faire de nouvelles contributions à la théorie des types dépendants, en plus du concept d'univalence.

Formath
Lundi 19 mai 2025, 15 heures, 3052 et en visio
Collectif Discussion informelle après le cours de Thierry Coquand

Algorithmique distribuée et graphes
Mardi 20 mai 2025, 15 heures, 3052
Romain Bourneuf (Université de Bordeaux) A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number

In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if V is a finite set of points of R^N such that for each v in V the ball B(v,1) intersects V on at least delta*|V| points, then for every epsilon>0, the points of V can be covered with f(delta,epsilon) balls B(v,1+epsilon) with v in V. DNL also applies to other metric spaces and to abstract set systems. In its strongest form, DNL provides an epsilon-clustering with size exponential in 1/epsilon, which amounts to a Regularity Lemma with 0/1 densities of some trigraph.

I will discuss the notion of VC-dimension, and explain how to generalize it to trigraphs to obtain statements such as DNL. I will then discuss some applications of DNL to the chromatic number of dense triangle-free graphs, and to domination in majority tournaments.

Algorithmes et complexité
Mercredi 21 mai 2025, 11 heures, Salle 3052
Isabella Ziccardi (IRIF) The Minority Dynamics

We study the minority-opinion dynamics over a fully-connected network of $n$ nodes with binary opinions. Upon activation, a node receives a sample of opinions from a limited number of neighbors chosen uniformly at random. Each activated node then adopts the opinion that is least common within the received sample. Unlike all other known consensus dynamics, we prove that this elementary protocol behaves in different ways, depending on whether activations occur sequentially or in parallel. Specifically, we show that its expected consensus time is exponential in n under asynchronous models, but, on the other hand, we show that it converges within $O(\log^2 n)$ rounds with high probability under synchronous models.

Our results shed light on the bit-dissemination problem, which was previously introduced to model the spread of information in biological scenarios. Specifically, our analysis implies that the minority-opinion dynamics is the first memoryless solution to this problem, in the parallel passive-communication setting, achieving convergence within a polylogarithmic number of rounds. This, together with a known lower bound for sequential stateless dynamics, implies a parallel-vs-sequential gap for this problem that is nearly quadratic in the number $n$ of nodes. This is in contrast to all known results for problems in this area, which exhibit a linear gap between the parallel and the sequential setting.

Preuves, programmes et systèmes
Jeudi 22 mai 2025, 10 heures 30, Salle 3052 & online (Zoom link)
Noam Zeilberger Non encore annoncé.

Séminaire des membres non-permanents
Jeudi 22 mai 2025, 16 heures, Salle 3052
Ricardo Canesin (IMJ-PRG) Quiver Representations: Linear Algebra on Steroids

Quivers and their representations offer a natural language for formulating and solving various matrix problems. In this talk, we will start with an elementary approach to the subject and proceed through the lens of the representation theory of associative algebras. We then present Gabriel’s celebrated theorem, which classifies quivers with only finitely many indecomposable representations. Finally, we discuss how the theory developed by Auslander and Reiten provides a method for constructing (many of) the indecomposable representations. The talk will be accessible and requires only a background in linear algebra.

Automates
Vendredi 23 mai 2025, 14 heures, Salle 3052
Olivier Idir (IRIF) Characterizations of the Mostowski Index via games and universal trees

The parity index problem of tree automata asks, given a regular tree language L and a set of priorities J, is L J-feasible, that is, recognized by a nondeterministic parity automaton with priorities J. The minimal such J for a language is called its Mostowski index. This is a long-standing open problem, of which only a few sub-cases and variations are known to be decidable. Starting from the work from Colcombet and Löding on this same problem, we provide a new characterization of the J-feasibility, using tools from the parity game literature. We add some counters to Lehtinen’s register game, originally used to solve parity games in quasipolynomial time, and use this novel game to characterize J-feasibility. This provides a simple alternative proof to Colcombet and Löding’s reduction. Starting from this reduction, we exhibit two other characterizations, linking the index problem with universal trees and with a parameterized version of the Strahler number, a measure of the branching degree of a finite-depth tree. While we do not solve the decidability of the index problem, our work makes the state-of-the-art more accessible and brings to light the deep relationships between the J-feasability of a language and attractor decompositions, universal trees and Lehtinen’s register game.

Sémantique
Mardi 27 mai 2025, 15 heures, Salle 3071
Ryuya Hora (University of Tokyo) Non encore annoncé.

One world numeration seminar
Mardi 27 mai 2025, 14 heures, Online
Savinien Kreczman (Université de Liège) Non encore annoncé.