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

Blog binaire

Sylvain Perifel (IRIF) and Guillaume Lagarde (Université de Bordeaux) publish on the Blog Binaire the first article of a series about algorithmic complexity. The series aims be easy-to-understand and accessible to everyone.


We are happy to welcome Mirna DŽAMONJA, winner of an individual grant Marie CURIE part of the H2020 European program. Learn more about her and her work here

The ANR projet MAVeriQ will be having its second kickoff meeting on Friday March 26th. It will be starting with 4 short scientific talks: Eugene Asarin (IRIF), Loïc Helouet (IRISA), Nicolas Basset (VERIMAG), Benoît Barbot (LACL). Anybody who is interested is kindly invited to attend.

Collège de France

Frédéric Magniez (IRIF CNRS member) holds the 2020–2021 chair on Computer Science at Collège de France (in partnership with Inria), where he will present a course on Quantum Algorithms starting April 7th with an Inaugural lecture on April 1st. Poster with full program.

Stephen Wolfram

Stephen Wolfram, pioneer in the development and application of computational thinking, will be speaking on Wednesday April 28, 18:00 CET at GReTA special event co-organized by IRIF.

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

Preuves, programmes et systèmes
Jeudi 22 avril 2021, 10 heures, Online
Gabriele Vanoni (Università di Bologna) The Time and Space of Interaction

Girard's Geometry of Interaction (GOI) can be made concrete by considering it as an implementation technique for functional programs, in particular the lambda calculus. Our work is about the complexity analysis of the abstract machine based on the GOI, the interaction abstract machine (IAM). We have adapted in a non trivial way de Carvalho's non idempotent intersection types so that type derivations completely characterize the time and space complexity of the IAM, thus providing a logical account of the IAM resource usage. Moreover, by the way of the type systems we have introduced, we are able to state some negative results about time and space cost models for the lambda calculus based on the IAM. This is joint work with Beniamino Accattoli and Ugo Dal Lago.

Vendredi 23 avril 2021, 14 heures 30, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl
Misha Vyalyi Re-pairing brackets and commutative automata.

Graph Transformation Theory and Applications
Vendredi 23 avril 2021, 15 heures, online
Paweł Sobociński (Department of Computer Science, Tallinn University of Technology, Estonia) Rewriting Modulo Symmetric Monoidal Structure

String diagrams are an elegant, convenient and powerful syntax for arrows of symmetric monoidal categories. In recent years, they have been used as compositional descriptions of computational systems from various fields, including quantum foundations, linear algebra, control theory, automata theory, concurrency theory, and even linguistics. All of these applications rely on diagrammatic reasoning, which is to string diagrams as equational reasoning is to ordinary terms.

If we are to take string diagrams out of research papers and into practical applications, we need understand how to implement diagrammatic reasoning. This is the focus of my talk.

There is a tight correspondence between symmetric monoidal categories where every object has a coherent special Frobenius algebra structure and categories of cospans of hypergraphs. This correspondence, therefore, takes us from a topological understanding of string diagrams to a combinatorial data-structure-like description. Moreover, diagrammatic reasoning translates via this correspondence exactly to DPO rewriting with interfaces.

The obvious follow-up question is: how much of this correspondence survives if we drop the assumption about Frobenius structure? Can we use this correspondence to implement diagrammatic reasoning on vanilla symmetric monoidal categories? The answer is yes, but we need to restrict the kinds of cospans we consider: the underlying hypergraph has to be acyclic and satisfy an additional condition called monogamy. Moreover, we must restrict the DPO rewriting mechanism to a variant that we call convex DPO rewriting. The good news is that none of these modifications come with a significant algorithmic cost.

The material in this talk is joint work with Filippo Bonchi, Fabio Gadducci, Aleks Kissinger and Fabio Zanasi, and has been published in a series of papers:

- “Rewriting modulo symmetric monoidal structure”, Proceedings of LiCS 2016

- “Confluence of Graph Rewriting with Interfaces”, Proceedings of ESOP 2017

- “Rewriting with Frobenius”, Proceedings of LiCS 2018

Zoom registration

YouTube live stream

Algorithmique distribuée et graphes
Mardi 27 avril 2021, 15 heures, ZOOM
Daniel Adolfo Quiroz Colouring with conditions on distances

A natural variant of proper vertex colorings, consists in considering colorings which require different colours for vertices at distance (exactly) p, for some fixed p. For that type of colouring, the answer to the question “how many colours suffice?”, can depend greatly on the parity of p. In the talk I will give an overview of the results on this type of colouring, focusing particularly in the case of planar graphs.

Mardi 27 avril 2021, 10 heures, Exposé à distance sur Galène – salle 3052 virtuelle
Soichiro Fujii (Research Institute in Mathematical Science (RIMS), Kyoto) Completeness and injectivity

We show that for any quantale Q, a Q-category is skeletal and complete if and only if it is injective with respect to fully faithful Q-functors. This is a special case of known theorems due to Hofmann and Stubbe, but we provide a different proof, using the characterisation of the MacNeille completion of a Q-category as its injective envelope.

One world numeration seminar
Mardi 27 avril 2021, 14 heures 30, Online
Boris Adamczewski (CNRS, Université Claude Bernard Lyon 1) Expansions of numbers in multiplicatively independent bases: Furstenberg's conjecture and finite automata

It is commonly expected that expansions of numbers in multiplicatively independent bases, such as 2 and 10, should have no common structure. However, it seems extraordinarily difficult to confirm this naive heuristic principle in some way or another. In the late 1960s, Furstenberg suggested a series of conjectures, which became famous and aim to capture this heuristic. The work I will discuss in this talk is motivated by one of these conjectures. Despite recent remarkable progress by Shmerkin and Wu, it remains totally out of reach of the current methods. While Furstenberg’s conjectures take place in a dynamical setting, I will use instead the language of automata theory to formulate some related problems that formalize and express in a different way the same general heuristic. I will explain how the latter can be solved thanks to some recent advances in Mahler’s method; a method in transcendental number theory initiated by Mahler at the end of the 1920s. This a joint work with Colin Faverjon.

Graph Transformation Theory and Applications
Mercredi 28 avril 2021, 18 heures, online
Stephen Wolfram (Wolfram Research, Champaign, USA) GReTA Special Event: Graph Rewriting as a Foundation for Science and Technology (and the Universe)

About the speaker:

Stephen Wolfram is the creator of Mathematica, Wolfram|Alpha and the Wolfram Language; the author of “A New Kind of Science”; the originator of the Wolfram Physics Project; and the founder and CEO of Wolfram Research. Over the course of more than four decades, he has been a pioneer in the development and application of computational thinking—and has been responsible for many discoveries, inventions and innovations in science, technology and business.

Zoom registration

YouTube live stream

Preuves, programmes et systèmes
Jeudi 29 avril 2021, 10 heures 30, Online at link (any password works)
Gabriel Scherer (Inria Saclay) Non encore annoncé.