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é, 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. 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 Twitter/X et LinkedIn pour suivre toute notre actualité :

Twitter/X LinkedIn

csl2024.jpg

10.10.2023
We are very proud to announce that five papers by six IRIF researchers have been selected for the CSL conference! Congratulations to Quentin Aristote, Guillaume Geoffroy, Roman Kniazev, Jérémy Ledent, François Laroussinie and Vincent Moreau.

perso-sylvain-perifel.jpg

24.11.2023
Sylvain Perifel will defend his habilitation to direct research [HDR] on Monday 4 December 2022 at 2pm in the Pierre-Gilles de Gennes Amphitheatre of the Condorcet building. His subject is L'aléatoire par le prisme des polynômes et de la compression.

perso_guillaume_baudart.jpg

30.11.2023
IRIF has the great pleasure to welcome a new researcher (INRIA ISFP): Guillaume Baudart, an expert in on probabilistic and reactive programming languages (language design, semantics, static analysis, compilation, inference).

21.11.2023
Du mardi 28 novembre au jeudi 30 novembre, nous recevrons à l'IRIF le comité d'évaluation de l'HCERES dans le cadre de l'évaluation de notre laboratoire. Programme

ASCII

23.11.2023
IRIF has the great pleasure to welcome a new researcher (INRIA): Gabriel Scherer, an expert in programming languages, with theoretical aspects of type systems, programming language implementation, general programming language concepts, and even some syntactic aspects.

perso_hugoherbelin.jpg

16.11.2023
La prochaine édition de Mathématiques en mouvement, conférence proposée par la FSMP, aura pour thème Des preuves et des programmes. Organisée sous la houlette de Hugo Herbelin, elle aura lieu le samedi 2 décembre 2023 de 14h à 18h.

14.11.2023
We are very proud to announce that two papers by two IRIF researchers have been selected for the SODA conference! Congratulations to François Sellier and Robin Vacus.

7.11.2023
We are very proud to announce that four papers by six IRIF researchers have been selected for the POPL conference! Congratulations to Claudia Faggian and Gabriele Vanoni, Mahsa Shirmohammadi, Giuseppe Castagna, Mickaël Laurent and Gabriel Scherer.


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

Vérification
Lundi 4 décembre 2023, 11 heures, 3052 and Zoom link
Marco Campion (INRIA) Monotonicity and the Precision of Program Analysis

It is widely known that the precision of a program analyzer is closely related to intensional program properties, namely, properties concerning how the program is written. This explains, for instance, the interest in code obfuscation techniques, namely, tools explicitly designed to degrade the results of program analysis by operating syntactic program transformations. Less is known about a possible relation between what the program extensionally computes, namely, its input-output relation, and the precision of a program analyzer. In this paper we explore this potential connection in an effort to isolate program fragments that can be precisely analyzed by abstract interpretation, namely, programs for which there exists a complete abstract interpretation. In the field of static inference of numeric invariants, this happens for programs, or parts of programs, that manifest a monotone (either non-decreasing or non-increasing) behavior. We first formalize the notion of program monotonicity with respect to a given input and a set of numerical variables of interest. A sound proof system is then introduced with judgments specifying whether a program is monotone relatively to a set of variables and a set of inputs. The interest in monotonicity is justified because we prove that the family of monotone programs admit a complete abstract interpretation over a specific class of non-trivial numerical abstractions and inputs. This class includes all non-relational abstract domains that refine interval analysis (i.e., at least as precise as the intervals abstraction) and that satisfy a topological convexity hypothesis.

Soutenances d'habilitation
Lundi 4 décembre 2023, 14 heures, Amphithéâtre Pierre-Gilles de Gennes du bâtiment Condorcet
Sylvain Perifel (IRIF) L'aléatoire par le prisme des polynômes et de la compression

Jury :
- Claire Mathieu, présidente, directrice de recherche au CNRS, Académie des sciences
- Meena Mahajan, rapporteuse, professeure à l'Institut des sciences mathématiques de Chennai
- Santiago Figueira, rapporteur, professeur à l'université de Buenos Aires
- Olivier Bournez, rapporteur, professeur à l'École polytechnique
- Damiano Mazza, examinateur, directeur de recherche au CNRS
- Olivier Carton, examinateur, professeur à l'université Paris Cité, IUF

« Résumé opérationnel » :
Dans une première partie, nous comparerons quelques méthodes efficaces de compression (automates à pile, LZ'78, espace polylogarithmique), puis nous étudierons la « catastrophe du premier bit » pour l'algorithme de Lempel-Ziv, où l'ajout d'un seul bit peut changer le taux de compression. La seconde partie traitera de complexité algébrique, en particulier de bornes inférieures pour certains modèles de calcul de polynômes, et du célèbre problème de test d'identité polynomiale qui résiste encore aux tentatives de dérandomisation.

Algorithmes et complexité
Mardi 5 décembre 2023, 11 heures, Salle 3052
Marc-Olivier Renou (INRIA Saclay) Causal and No Signalling-LOCAL models as the largest generalization of synchronous quantum distributed computing

In the LOCAL model of distributed computing, n processors are connected together through a graph. They communicate with their neighbours in a synchronised way a limited number of times (through infinite bandwith communication channels), and then produce an output. Their goal is to find a strategy solving some information processing task, e.g. to obtain a proper coloring of the graph. To answer this question, the considered physical theory of information matters: for instance, Quantum Information Theory (QIT) can in principle allow for strategies solving the task quicker.

Finding lower bounds on the maximal speed at which QIT can solve a task is tricky. To circumvent this difficulty, several proofs based on the No-Signalling (NS) Principle (which states that an event A can influence an event B only if some signal can physically be sent from A to B) were proposed and a new NS-LOCAL model of distributed computing was proposed.

I’ll re-interpret this NS-LOCAL model based on the theoretical physics formalism of light cones in circuits. I will justify that the NS-LOCAL model is the “largest reasonable model with a pre-shared resource between the nodes”. Then, I’ll introduce a weaker Causal-LOCAL model, the “largest reasonable model without pre-shared resource between the nodes”.

All this will be illustrated with easy to understand examples. I was recently told by Vaclav Rozhon: We computer scientists are very scared of the word “quantum”. Note that I’ll almost not talk about quantum theory, hence no need to be scared.

Combinatoire énumérative et analytique
Jeudi 7 décembre 2023, 10 heures, IHP
Séminaire Flajolet Et Conférence Ihp: Computer Algebra For Functional Equations In Combinatorics And Physics Du 4 Au 8 Décembre.

Conférence à l'IHP incluant une journée spéciale “Séminaire Flajolet” le jeudi 7.

Inscription obligatoire sur le site de la conférence: https://indico.math.cnrs.fr/event/8115/registrations/

Voir aussi: https://semflajolet.math.cnrs.fr/

Preuves, programmes et systèmes
Jeudi 7 décembre 2023, 10 heures 30, Salle 3052
Meven Lennon-Bertrand (Université de Cambridge) Non encore annoncé.

Séminaire des membres non-permanents
Jeudi 7 décembre 2023, 16 heures, Salle 3052
Esaie Bauer Proof theory in Multiplicative-Additive Linear Logic

In this presentation, I will provide an introduction to proof theory within the context of non-wellfounded proof systems. A non-wellfounded proof is generated by finitely branching logical rules, but potentially resulting in an infinitely deep proof tree. After defining the system, I will present a proof of cut-elimination for the $\mu$-MALL system, drawing from the work of Baelde et al. in 2016. Furthermore, I will discuss how we aim to extend this result with Alexis Saurin.

La syntaxe rencontre la sémantique
Jeudi 7 décembre 2023, 14 heures, Salle 3052
Pablo Barenbaum (Universidad Buenos Aires) Sharing in linear logic and call-by-need

Automates
Vendredi 8 décembre 2023, 14 heures, Salle 3052
Anantha Padmanabha Consistent Query Answering under Primary Keys

Primary key constraints in databases state there can be at most one tuple for every primary key in a given relation. However, these days it is common to have situations where this property cannot be maintained. Databases that violate constraints are called « inconsistent databases ». In particular, if a database violates primary key constraint, it will contain more than one tuple for the same primary key. In this setting, the notion of a repair is defined by picking exactly one tuple for each primary key (maximal consistent subset of the database). A Boolean conjunctive query q is certain for an inconsistent database D if q evaluates to true over all repairs of D. In this context, there is a dichotomy conjecture that states that for a fixed boolean conjunctive query q, testing whether q is certain for an input database D is either polynomial time or coNP-complete.

The conjecture is open in general and has been open for more than two decades. In this talk we will introduce two new algorithms that we have devised, one based on fix-point computation and the other based on bipartite matching. We will also see how these algorithms can be used to prove the dichotomy for the cases that were previously open.

These results were obtained in collaboration with Diego Figueira, Luc Segoufin and Cristina Sirangelo and combine the results that were presented at ICDT 2023 and what will be presented at PODS 2024.

Algorithmique distribuée et graphes
Vendredi 8 décembre 2023, 15 heures, 1007
Pierre Aboulker (ENS-Paris) Clique number of tournaments

the dichromatic number of a digraph is the minimum integer k such that the set of vertices of D can be partitioned into k acyclic subdigraphs. It is easy to see that the chromatic number of a graph G is the same as the dichromatic of the digraph obtained from G by replacing each edge by a digon (two anti-parallel arcs). Based on this simple observation, many theorems concerned with chromatic number of undirected graphs have been generalised to digraphs via the dichromatic number. However, no concept of clique number for digraphs was available. The purpose of this presentation is to explore such a concept and its relationship with the dichromatic number, mirroring the relationship between the clique number and chromatic number in undirected graphs. We will focus on studying the notion of chi-boundedness in particular. This is a joint work with Guillaume Aubian, Pierre Charbit and Raul Lopes.

Vérification
Lundi 11 décembre 2023, 11 heures, 3052 and Zoom link
Sarah Winter (IRIF) Non encore annoncé.