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.

Test of Time Award - LICS'22

19.9.2022
Philippe Schnoebelen (LMF), François Laroussinie (IRIF) and Nicolas Markey (IRISA), received the Test-of-Time award at the conference LICS 2022 for their research on temporal logic.

Création du prix Lovelace-Babbage

2.9.2022
L’Académie des sciences et la Société informatique de France annoncent la création d’un nouveau prix en informatique : le prix Lovelace-Babbage.

Baptiste Louf Prix de Thèse

31.8.2022
Baptiste Louf, a former IRIF PhD. student is the 2021 winner of the Chancellerie des Universités de Paris thesis award in the “all specialties” science category. Learn more about his work in this written interview.

Workshop CoA 2022

2.9.2022
The 2nd Workshop Complexity and Algorithms (CoA 2022) will take place in September 26-28 2022 at Institut Henri Poincaré (IHP), Paris. Scientific program includes talks from invited speakers Marthe Bonamy (LaBRI), Carola Doerr (LIP6), Sébastien Tavenas (LAMA) and Adrian Vladu (IRIF).

Podcast DECODE quantum

2.9.2022
Pour son 48ème épisode, le podcast DECODE Quantum a reçu le directeur de l'IRIF Frédéric Magniez dans un entretien approfondi sur le quantique. Il est question, entre autres, d'algorithmes quantiques, de leur intérêt et de leur construction. Par ici pour écouter l'émission.

ICTP-EAUMP School on Mathematical Programming and Algorithms

7.9.2022
IRIF is a co-sponsor of the ICTP-EAUMP School on Mathematical Programming and Algorithms - an African Mathematical School. The 2022 summer school organized by the University of Nairobi took place at Kenya School of Government, Nairobi, Kenya 11-29 July, 2022. Three IRIF members took part of this project: Jean-Baptiste Yunès, Roberto Mantaci and Anna Vanden Wyngaerd.

Prix Irène Joliot-Curie 2022

2.9.2022
Plus que quelques jours pour déposer votre candidature au Prix Irène Joliot-Curie, ce prix qui vise à promouvoir la place des femmes dans la recherche et la technologie en France. Clôture des candidatures le 8/09/2022.


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

Sémantique
Lundi 26 septembre 2022, 14 heures, Bâtiment Sophie Germain, salle 1007
Marek Zawadowski (Université de Varsovie) Polynomial and analytic functors, revisited

In my talk I will show that some versions of operads/multicategories (non-Sigma, symmetric, with amalgamations) and finitary polynomial and analytic functors, i.e., the devices that have been used to define opetopic sets by various authors, are either very closely related or even two sides of the same coin, if placed in the suitable context. These structures have been used in many contexts and not always with the understanding to what extent they are similar.

I will start with some easy examples showing how these structures can be related to one another in the category Set. It turns out that polynomial functors and monads are related to Kleisli algebras, whereas analytic functors and monads are related to Eilenberg-Moore algebras for the same monad.

Then I will show that in fact this kind of structures and relations between them can be constructed in any 2-category with some mild completeness properties, whenever a lax monoidal monad sits inside it.

Sémantique
Mardi 27 septembre 2022, 10 heures 30, Salle 3052
Rick Blute (University of Ottawa) Finiteness Spaces and Monoidal Topology

Much of my recent research has been in demonstrating the idea that working with Ehrhard's notion of finiteness space forces certain sums which would a priori be infinite to become finite, and hence well-defined, without resorting to limit structure or infinitary computations. It is hoped that this will lead to a great many applications, and that one of those applications is in the field of monoidal topology. Typically monoidal topology takes place in the category of quantale-valued relations.

In this talk, we'll briefly review some previous results which demonstrate the utility of finiteness spaces in the types of settings we are considering and then introduce monoidal topology, and finally consider possible extensions of monoidal topology via finiteness spaces. By using Ehrhard's linearization construction, we can instead consider relations on finiteness spaces which take values in a positive partially ordered semiring. In particular, we no longer require infinitary operations. This type of semiring is important in the theory of weighted automata among other places.

One world numeration seminar
Mardi 27 septembre 2022, 14 heures, Online
Niels Langeveld (Montanuniversität Leoben) $N$-continued fractions and $S$-adic sequences

Given the $N$-continued fraction of a number $x$, we construct $N$-continued fraction sequences in the same spirit as Sturmian sequences can be constructed from regular continued fractions. These sequences are infinite words over a two letter alphabet obtained as the limit of a directive sequence of certain substitutions (they are S-adic sequences). By viewing them as a generalisation of Sturmian sequences it is natural to study balancedness. We will see that the sequences we construct are not 1-balanced but C-balanced for $C=N^2$. Furthermore, we construct a dual sequence which is related to the natural extension of the $N$-continued fraction algorithm. This talk is joint work with Lucía Rossi and Jörg Thuswaldner.

Combinatoire énumérative et analytique
Jeudi 29 septembre 2022, 14 heures, Salle 3052
Houcine Ben Dali (IECL (Université de Lorraine), IRIF (Université de Paris)) Integrality in the matching-Jack conjecture

Using Jack polynomials, Goulden and Jackson have introduced a one parameter deformation $τ_b$ of the generating series of bipartite maps. The Matching-Jack conjecture suggests that the coefficients $c^λ_{µ,ν}$ of the function $τ_b$ in the power-sum basis are non-negative integer polynomials in the deformation parameter $b$. Dołega and Féray have proved in 2016 the “polynomiality” part in the Matching-Jack conjecture. In this talk I present a proof for the “integrality” part.

The proof is based on a recent work in which I obtain the Matching-Jack conjecture for marginal sums $c^λ_{µ,m}$ from an analog result for the $b$-conjecture, established in 2020 by Chapuy and Dołega. Jack polynomials orthogonality gives a linear system relating the coefficients $c^λ_{µ,ν}$ to the marginal coefficients $c^λ_{µ,m}$. Using a graded version of the Farahat-Higman algebra we prove that this system is invertible in $\mathbb{Z}$.

Combinatoire énumérative et analytique
Jeudi 6 octobre 2022, 14 heures, IHP
Seminaire Flajolet Jehanne Dousse, Nicolas Bonichon, Thierry Levy

Preuves, programmes et systèmes
Jeudi 6 octobre 2022, 10 heures, Salle 3052
All Hands On Deck (IRIF) Matinée de rentrée de PPS

Catégories supérieures, polygraphes et homotopie
Vendredi 7 octobre 2022, 14 heures, Salle 1007
Pierre-Louis Curien (IRIF) Une preuve élémentaire de ce que les ensembles opétopiques sont les polygraphes ``many-to-one’’

Automates
Vendredi 7 octobre 2022, 14 heures, Salle 3052
Jacques Sakarovitch Non encore annoncé.

Vérification
Lundi 10 octobre 2022, 11 heures, 3052 and Zoom link
Cristina Seceleanu (Mälardalen University) Reinforcement Learning for Mission Plan Synthesis of Autonomous Vehicles

Computing a mission plan for an autonomous vehicle consists of path planning and task scheduling, which are two outstanding problems existing in the design of multiple autonomous vehicles. Both problems can be solved by the use of exhaustive search techniques such as model checking and algorithmic game theory. However, model checking suffers from the infamous state-space-explosion problem that makes it inefficient at solving the problem when the number of vehicles is large, which is often the case in realistic scenarios. In this talk, we show how reinforcement learning can help model checking to overcome these limitations, such that mission plans can be synthesized for a larger number of vehicles if compared to what is feasibly handled by model checking alone. Instead of exhaustively exploring the state space, the reinforcement-learning-based method randomly samples the state space within a time frame and then uses these samples to train the vehicle models so that their behavior satisfies the requirements of tasks. Since every state of the model needs not be traversed, state-space explosion is avoided. Additionally, the method also guarantees the correctness of the synthesis results. The method is implemented in UPPAAL STRATEGO and integrated with a toolset to facilitate path planning and task scheduling in industrial use cases. We also discuss the strengths and weaknesses of using reinforcement learning for synthesizing strategies of autonomous vehicles.

Combinatoire énumérative et analytique
Jeudi 13 octobre 2022, 12 heures, Salle 3052 et zoom
Jiyang “johnny” Gao (Harvard) TBD