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. Six de ses membres ont été lauréats de l'European Research Council (ERC), six 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.

Journées Nationales du GDR IM 2023

10.3.2023
Les prochaines Journées Nationales du GDR IM (JNIM 2023) auront lieu à l'Université Paris Cité du 4 avril au 7 avril et sont organisées par l'IRIF. Programme et inscription ici.

JACM Articles from 2022

7.3.2023
The paper “Decentralized Asynchronous Crash-resilient Runtime Verification” authored by Borzoo Bonakdarpour (MSU), Pierre Fraigniaud (IRIF), Sergio Rajsbaum (UNAM), David Rosenblueth (UNAM), and Corentin Travers (LIS) has been selected in the “sample of [eight] exciting [..] articles on a diverse range of topics that were published in 2022” in the Journal of the ACM (JACM).

Interview PhD thesis Farzad Jafarrahmani

6.3.2023
Farzad Jafarrahmani, former PhD student at IRIF explains his thesis Fixpoints of Types in Linear Logic from a Curry-Howard-Lambek Perspective in this written interview.

Conférence vidéo “Manuel de Cryptanalyse à l’usage de la NSA”

6.3.2023
“Manuel de Cryptanalyse à l’usage de la NSA” est une conférence ludique, présentée par Sylvain Perifel – Maître de conférences (Université Paris Cité/IRIF) à l’occasion de l’édition 2022 de la Fête de la Science. Elle retrace et met en pratique les différentes avancées historiques de cette science, du code de César à RSA en passant par les substitutions mono-alphabétiques et par le chiffre de Vigenère.

Shared engineer position in formal methods

27.2.2023
Shared engineer position in formal methods, between IRIF, LIPN and LMF. Deadline to apply: 17/03/2023.

Appel à manifestation d'intérêt 2023 - Médiation scientifique

7.3.2023
Pour la troisième année consécutive, la Faculté des Sciences d’Université Paris Cité lance un appel à manifestation d’intérêt pour accompagner et soutenir ses membres dans leurs initiatives ayant vocation à rendre accessible un sujet de recherche scientifique à un public non spécialiste. Date limite 20 mars 2023 minuit.

Accepted paper STOC 2023

27.2.2023
One paper authored by IRIF member will be presented at STOC 2023, June 20-23, 2023 in Orlando, Florida.


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

Algorithmes et structures discrètes
Mercredi 22 mars 2023, 15 heures, 3052
Michail Lampis (LAMSADE) First Order Logic on Pathwidth Revisited Again

Courcelle's theorem, which states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth, is one of the most celebrated results in parameterized complexity, because it implies the existence of linear-time FPT algorithms for a host of NP- hard problems. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula.

In this talk we take a high-level view of this area of research and survey results that attempt to improve upon this performance by considering more restricted classes of inputs. This is known to be impossible, even if we restrict the input to graphs of treewidth 1 (trees) and only consider FO logic; or if we consider graphs of pathwidth 1 (caterpillars) and consider MSO logic. This would seem to indicate that Courcelle's theorem is “best possible”. Surprisingly, we discover that in the only remaining case which has so far been overlooked, namely FO logic on graphs of constant pathwidth, all known hardness results fail, because the problem becomes tractable with an elementary parameter dependence on the input formula. Our result generalizes previously known meta-theorems for the much more restricted parameter tree-depth.

Results based on a preprint available here: https://arxiv.org/abs/2210.09899

Preuves, programmes et systèmes
Jeudi 23 mars 2023, 10 heures 30, TBA
Giulio Manzonetto CANCELLED

Postponed to a date TBA.

Séminaire des doctorants
Jeudi 23 mars 2023, 16 heures, 3052 and Zoom link
Robin Vacus Introduction to Game-Theory: Braess-like paradoxes

One of the most fascinating phenomena in game theory is the Braess paradox, which occurs when adding an additional route to a network leads to increased congestion and travel times for everyone. In this talk, after introducing some basic concepts and presenting the paradox, I will describe a few other scenarios in which improving the productivity of individuals counter-intuitively leads to degraded group productivity.

Automates
Vendredi 24 mars 2023, 14 heures, Salle 3052
Quentin Manière Counting queries in ontology-based data access

Ontology-mediated query answering (OMQA) is a promising approach to data access and integration that has been actively studied in the knowledge representation and database communities for more than a decade. The vast majority of work on OMQA focuses on conjunctive queries, whereas more expressive queries that feature counting or other forms of aggregation remain largely unexplored. We introduce a general form of counting conjunctive query (CCQ), relate it to previous proposals, and study the complexity of answering such queries in the presence of ontologies expressed in the description logic ALCHI or its sublogics. As the general case of CCQ answering is intractable and often of high complexity over such ontologies, we consider two practically relevant restrictions, namely rooted CCQs and Boolean atomic CCQs, for which we establish improved complexity bounds.

Graph Transformation Theory and Applications
Vendredi 24 mars 2023, 15 heures, online
Elvira Pino And Fernando Orejas (Department of Computer Science, Universitat Politècnica de Catalunya, Spain) A Logical Approach to Graph Databases

Graph databases are now playing an important role because they allow us to overcome some limitations of relational databases. In particular, graph databases differ from relational databases in that the topology of data is as important as the data itself. Thus, typical graph database queries are navigational, asking whether some nodes are connected by paths satisfying some specific properties.

While relational databases were designed upon logical and algebraic foundations, the development of graph databases has been quite ad-hoc. In this sense, the aim of this paper is to provide them with some logical foundations. More precisely, in previous work we introduced a navigational logic, called GNL (Graph Navigational Logic) that allows us to describe graph navigational properties, and which is equipped with a deductive tableau method that we proved to be sound and complete.

In this presentation we will introduce a new formal model for property graphs. Then, we will show how graph queries à la Cypher can be expressed using a fragment of GNL, defining for them a logical and an operational semantics, based on the inference rules for GNL. Finally, we show that both semantics are equivalent.

Zoom meeting registration link

YouTube live stream

Vérification
Lundi 27 mars 2023, 11 heures, 1007 and Zoom link
Lénaïg Cornanguer & Christine Largouët (IRISA Rennes) TAG: Learning Timed Automata from Logs

Event logs are often one of the main sources of information to understand the behavior of a system. While numerous approaches have extracted partial information from event logs, we aim at inferring a global model of a system from its event logs.

We consider real-time systems, which can be modeled with Timed Automata: our approach is thus a Timed Automata learner. There is a handful of related work, however, they might require a lot of parameters or produce Timed Automata that either are undeterministic or lack precision. In contrast, we propose an approach, called TAG, that requires only one parameter and learns, without any a-priori knowledge, a deterministic Timed Automaton having a good tradeoff between accuracy and automata complexity. This allows getting an interpretable and accurate global model of the considered real-time system. Experiments compare our approach to related work and demonstrate its merits.

Algorithmes et structures discrètes
Mardi 28 mars 2023, 15 heures, 3052
Lélia Blin (LIP6) Self-Stabilizing Distributed Algorithms

In the context of large-scale networks, fault tolerance is a necessity. Self-stabilization is an algorithmic approach to fault tolerance in distributed systems. Its aim is to manage processors' memory corruption due to transient failures. The efficiency of a self-stabilizing algorithm is characterized by several parameters, including (1) the time taken by the system to return to a legal configuration after an arbitrary corruption of its processors' memory, and (2) the memory space used by the processors to execute the algorithm. Minimizing memory space is motivated by many aspects, such as networks (e.g. sensor networks) with limited memory space, minimizing data exchanges between processors, and limiting information storage to use redundancy techniques. This seminar will present self-stabilization through two main classical problems: constructing spanning trees, especially those of minimum weight, and electing a leader. It will cover the links between self-stabilization and distributed decision techniques, including computing lower bounds on memory space needed to solve the aforementioned problems using self-stabilizing algorithms.

One world numeration seminar
Mardi 28 mars 2023, 14 heures, Online
Roland Zweimüller (Universität Wien) Variations on a theme of Doeblin

Starting from Doeblin's observation on the Poissonian nature of occurrences of large digits in typical continued fraction expansions, I will outline some recent work on rare events in measure preserving systems (including spatiotemporal and local limit theorems) which, in particular, allows us to refine Doeblin's statement in several ways.

(Part of this is joint work with Max Auer.)

Preuves, programmes et tout ça
Mardi 28 mars 2023, 13 heures 30, salle 3052
Fabio Massaioli (Scuola Normale Di Pisa) (Scuola Normale di Pisa) A non-trivial proof-semantics for classical sequent calculus (LK)

Cut-reduction procedures for classical sequent calculus are notoriously non-deterministic and non-confluent, both in the original formulation by Gentzen and in later reformulations. It is natural to ask whether those instances of non-confluence are superficial in nature, i.e. whether syntactically distinct normal forms of the same derivation are in fact correlated in a non-trivial way, as is the case in the intuitionistic and linear versions of sequent calculus. A famous counter-example by Lafont purports to show that the answer is negative, that is, every interpretation of derivations in LK that is invariant under classical cut-elimination must be a trivial one that identifies at least all proofs of the same sequent. A long-standing open question has then been whether it could be possible to work around Lafont's example by natural and non-trivial adjustments of the calculus and/or of cut-reduction steps, without resorting to symmetry-breaking techniques like polarization or embeddings into intuitionistic or linear logic.

Working within the propositional fragment of the context-sharing formulation of LK — where parallel logical rules permute freely — we show that the graph constructed by tracing the history of atomic formula occurrences through axiom and cut rules is invariant under arbitrary rule permutations in cut-free proofs, thus providing a canonical representation of normal-form proofs.

We then introduce a refinement of the notion of axiom-induced graph that allows extending the invariance result to proofs with cuts, although at the cost of a strong assumption on the shape of derivations. Because cut-reduction in this formulation of LK can be implemented entirely by logical rule permutations plus a pair of local rewriting steps that preserve the refined axiom graphs, the result yields a non-trivial invariant of cut-reduction.

Algorithmique distribuée et graphes
Mercredi 29 mars 2023, 14 heures, 3052
Valentin Bartier (LIRIS) Independent set reconfiguration in sparse graphs

The problem of reconfiguring independent sets belongs to the broader field of combinatorial reconfiguration problems. It can be formulated as follows: given a collection of tokens placed on the vertices of an independent set of a graph, is it possible to move one by one these tokens to another target independent set, such that two tokens are never neighbors throughout the transformation? After a general introduction to combinatorial reconfiguration and the independent set reconfiguration problem, we will focus on the “Token Sliding” variant. In this variant, one step of the transformation consists in moving a token from a vertex to a neighboring vertex. We will focus on the parameterized complexity of this problem in sparse classes of graphs and on the new tools we have recently designed for the development of FPT algorithms.