Les membres de l'IRIF et les visiteurs sont priés de se conformer aux directives COVID-19 du CNRS et de l'Université de Paris.

Institut de Recherche en Informatique Fondamentale (IRIF)


L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université de Paris, qui héberge deux équipes-projets 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), cinq 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.

Pierre-Louis Curien

Pierre-Louis Curien (IRIF) is awarded with this year's Grand prix Inria – Académie des sciences. To learn more about Pierre-Louis Curien's contributions to theoretical computer science, read the portrayal published by Inria, and the interviews published by FSMP and La Recherche.

Delia Kesner

Delia Kesner (IRIF) has been elected corresponding member for information sciences of the Accademia delle Scienze di Torino.

Three papers co-authored by IRIF members will be presented at POPL2021, the main conference on programming languages and programming systems. The papers' study randomized computation, including machine learning, and verification for programs over persistent memory.

Claire Mathieu

A paper by C. Mathieu (IRIF CNRS member) with R. Rajaraman, N. Young, and A. Yousefi will be presented at SODA2021 on dynamization policies in the competitive analysis framework for log-structured merge trees underpinning industrial NoSQL databases.

Nicolas Behr

IRIF has the great pleasure to welcome a new research scientist (CNRS): Nicolas Behr, an expert in stochastic rewriting theory.

Geoffroy Couteau

A paper by G. Couteau (IRIF CNRS researcher) and D. Hartmann has been presented at the conference CRYPTO2020 and describes new, more compact constructions of non-interactive zero-knowledge proofs in elliptic curves equipped with a bilinear map.

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

Lundi 30 novembre 2020, 11 heures, BBB link
Engel Lefaucheux (Max-Planck Institute for Software Systems, Sarrebrucken) On Information Control in Probabilistic Systems: a closer look on Opacity and Diagnosis

The control of the information given by a system has recently seen increasing importance due to the omnipresence of communicating systems, the need for privacy, etc. This control can be used in order to disclose to an observer an information of the system, or, oppositely, to hide one. In this talk, I will consider the control of the information released by a system represented by a stochastic model such as a Markov chain. Here, an external observer is interested in detecting a particular set of relevant paths of the system. However, he can only observe those paths through an observation function which obfuscates the real behaviour of the system. Exact disclosure of the information occurs when the observer can deduce from a finite observation that the path is relevant, the approximate disclosure variant corresponding to the path being identified as relevant with high accuracy. I will discuss the problems of diagnosability and opacity, which corresponds, in spirit, to the cases where one wants to disclose all the information or hide as much of it as possible with a focus on the approximate notion of disclosure.

One world numeration seminar
Mardi 1 décembre 2020, 14 heures 30, Online
Michael Barnsley (Australian National University) Rigid fractal tilings

I will describe recent work, joint with Louisa Barnsley and Andrew Vince, concerning a symbolic approach to self-similar tilings. This approach uses graph-directed iterated function systems to analyze both classical tilings and also generalized tilings of what may be unbounded fractal subsets of R^n. A notion of rigid tiling systems is defined. Our key theorem states that when the system is rigid, all the conjugacies of the tilings can be described explicitly. In the seminar I hope to prove this for the case of standard IFSs.

Algorithmes et complexité
Mercredi 2 décembre 2020, 14 heures, Online
Claire Mathieu (IRIF) Competitive Data-Structure Dynamization

Data-structure dynamization is a general approach for making static data structures dynamic. It is used extensively in geometric settings and in the guise of so-called merge (or compaction) policies in big-data databases such as Google Bigtable and LevelDB (our focus). Previous theoretical work is based on worst-case analyses for uniform inputs – insertions of one item at a time and constant read rate. In practice, merge policies must not only handle batch insertions and varying read/write ratios, they can take advantage of such non-uniformity to reduce cost on a per-input basis. To model this, we initiate the study of data-structure dynamization through the lens of competitive analysis, via two new online set-cover problems. For each, the input is a sequence of disjoint sets of weighted items. The sets are revealed one at a time. The algorithm must respond to each with a set cover that covers all items revealed so far. It obtains the cover incrementally from the previous cover by adding one or more sets and optionally removing existing sets. For each new set the algorithm incurs build cost equal to the weight of the items in the set. In the first problem the objective is to minimize total build cost plus total query cost, where the algorithm incurs a query cost at each time t equal to the current cover size. In the second problem, the objective is to minimize the build cost while keeping the query cost from exceeding k (a given parameter) at any time. We give deterministic online algorithms for both variants, with competitive ratios of Θ(log∗n) and k, respectively. The latter ratio is optimal for the second variant.

Séminaire des doctorants
Mercredi 2 décembre 2020, 11 heures, Online
Phd Students Welcome session!

Combinatoire énumérative et analytique
Jeudi 3 décembre 2020, 10 heures, Virtuel
Marni Mishna, Laurent Viennot Séminaire Flajolet

Preuves, programmes et systèmes
Jeudi 3 décembre 2020, 10 heures 30, Online
Laure Gonnord (Université Lyon Claude Bernard) Non encore annoncé.

Vendredi 4 décembre 2020, 14 heures 30, Salle 3052
Georg Zetzsche Rational subsets of Baumslag-Solitar groups

Soutenances de thèses
Vendredi 4 décembre 2020, 14 heures, Online
Isaac Konan (IRIF) Rogers-Ramanujan type identities: bijective proofs and Lie-theoretic approach

The topic of this thesis belongs to the theory of integer partitions, at the intersection of combinatorics and number theory. In particular, we study Rogers-Ramanujan type identities in the framework of the method of weighted words. This method revisited allows us to introduce new combinatorial objects beyond the classical notion of integer partitions: the generalized colored partitions. Using these combinatorial objects, we establish new Rogers-Ramanujan identities via two different approaches. The first approach consists of a combinatorial proof, essentially bijective, of the studied identities. This approach allowed us to establish some identities generalizing many important identities of the theory of integer partitions: Schur’s identity and Göllnitz’ identity, Glaisher’s identity generalizing Euler’s identity, the identities of Siladi´c, of Primc and of Capparelli coming from the representation theory of affine Lie algebras. The second approach uses the theory of perfect crystals, coming from the representation theory of affine Lie algebras. We view the characters of standard representations as some identities on the generalized colored partitions. In particular, this approach allows us to establish simple formulas for the characters of all the level one standard representations of type A_{n-1}^{(1)},A_{2n}^{(2)},D_{n+1}^{(2)},A_{2n-1}^{(2)},B_{n}^{(1)},D_{n}^{(1)}.

Graph Transformation Theory and Applications
Vendredi 4 décembre 2020, 15 heures, (online)
Daniel Merkle & Jakob Lykke Andersen (Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark) Chemical Graph Transformation and Applications

Any computational method in chemistry must choose some level of precision in the modeling. One choice is made in the methods of quantum chemistry based on quantum field theory. While highly accurate, the methods are computationally very demanding, which restricts their practical use to single reactions of molecules of moderate size even when run on supercomputers. At the same time, most existing computational methods for systems chemistry and biology are formulated at the other abstraction extreme, in which the structure of molecules is represented either not at all or in a very rudimentary fashion that does not permit the tracking of individual atoms across a series of reactions.

In this talk, we present our on-going work on creating a practical modelling framework for chemistry based on Double Pushout graph transformation, and how it can be applied to analyse chemical systems. We will address important technical design decisions as well as the importance of methods inspired from Algorithm Engineering in order to reach the required efficiency of our implementation. We will present chemically relevant features that our framework provides (e.g. automatic atom tracing) as well as a set of chemical systems we investigated are currently investigating. If time allows we will discuss variations of graph transformation rule compositions and their chemical validity.

Zoom registration link:


Link to YouTube live stream: