Institut de Recherche en Informatique Fondamentale (IRIF)


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

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

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.

Podcast DECODE quantum

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

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.

Baptiste Louf Prix de Thèse

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

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

Prix Irène Joliot-Curie 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.)

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}$.

One world numeration seminar
Mardi 4 octobre 2022, 14 heures, Online
David Siukaev (Higher School of Economics) Exactness and Ergodicity of Certain Markovian Multidimensional Fraction Algorithms

A multidimensional continued fraction algorithm is a generalization of well-known continued fraction algorithms of small dimensions: Gauss and Euclidean. Ergodic properties of Markov MCF algorithms (ergodicity, nonsingularity, exactness, bi-measurability) affect their convergence (if the MСF algorithm is a Markov algorithm, there is a relationship between the spectral properties and its convergence).

In 2013 T. Miernowski and A. Nogueira proved that the Euclidean algorithm and the non-homogeneous Rauzy induction satisfy the intersection property and, as a consequence, are exact. At the end of the article it is stated that other non-homogeneous markovian algorithms (Selmer, Brun and Jacobi-Perron) also satisfy the intersection property and they also exact. However, there is no proof of this. In our paper this proof is obtained by using the structure of the proof of the exactness of the Euclidean algorithm with its generalization and refinement for multidimensional algorithms. We obtained technically complex proofs that differ from the proofs given in the article of T. Miernowski and A. Nogueira by the difficulties of generalization to the multidimensional case.

One world numeration seminar
Mardi 4 octobre 2022, 14 heures 30, Online
Alexandra Skripchenko (Higher School of Economics) Bruin-Troubetzkoy family of interval translation mappings: a new glance

In 2002 H. Bruin and S. Troubetzkoy described a special class of interval translation mappings on three intervals. They showed that in this class the typical ITM could be reduced to an interval exchange transformations. They also proved that generic ITM of their class that can not be reduced to IET is uniquely ergodic.

We suggest an alternative proof of the first statement and get a stronger version of the second one. It is a joint work in progress with Mauro Artigiani and Pascal Hubert.

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’’

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

Graph Transformation Theory and Applications
Vendredi 7 octobre 2022, 15 heures, online
Arend Rensink (Department of Computer Science, University of Twente, Netherlands) GROOVE: A tutorial overview

The graph transformation tool GROOVE is actively used in education and research, as an accessible and relatively powerful yet easy to use tool that incorporates many of the basic concepts and quite a number of more advanced GT-based features. However, being academy-ware, documentation is not its strongest point, and so some features are less visible and consequently under-used. In this presentation, I plan to demonstrate both the basic functionality (essentially, state space generation of a graph transformation system, with run-time isomorphism checking), as well as some of the more advanced features: - Typing, including subtyping, abstract types and type specialisation - Path expressions and label variables - Data manipulation, including algebra selection - Quantified rules, including the use of counting and multiary (i.e., set-based) operators - Rule control, including functions and (atomic) recipes.

Zoom meeting registration link

YouTube live stream