IRIF members and visitors are asked to comply with the COVID-19 Directives of CNRS and Université de Paris.

IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and Université de Paris, also hosting one Inria project-team.

The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences.

IRIF hosts about 200 people. Six of its members have been distinguished by the European Research Council (ERC), five are members of the Institut Universitaire de France IUF), two are members of the Academia Europæa, and one is member of Académie des sciences.

9.4.2021
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

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

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

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

(These news are displayed using a randomized-priority ranking.)

Distributed algorithms and graphs
Tuesday April 13, 2021, 3PM, ZOOM
Adrian Pastine (Universidad Nacional de San Luis) Null Decomposition of Graphs

Given a vector $\vec{x}$ in the null space of the adjacency matrix of a graph $G$, the support of $\vec{x}$ are the vertices which correspond to non-zero coordinates of $\vec{x}$. The support of $G$, $\Supp{G}$, is the union of the supports of all vectors in the null space of its adjacency matrix. The null decomposition of $G$, first introduced by Jaume and Molina in 2018, studies two subgraphs of $G$, $C_S(G)$, induced by the vertices in $\Supp{G}$ and their neighbours, and $C_N(G)$, induced by the remaining vertices.

In this talk, we study the null decomposition of bipartite graphs without cycles of length $0$ modulo $4$. We show that $C_S(G)$ contains a unique maximum independent set and that $C_N(G)$ contains a unique maximum matching. We use the decomposition to show that $\Supp{G}$ is the intersection of all maximum independent sets of $G$, and the union of the unmatched vertices over all maximum matchings. As an application, we present an algorithm that finds a sparse basis for the null space of adjacency matrix of forests in optimal time.

This talk is based on joint work with Daniel Jaume and Gonzalo Molina, from Universidad Nacional de San Luis, and Martin Safe, from Universidad Nacional del Sur.

One world numeration seminar
Tuesday April 13, 2021, 2:30PM, online
Andrew Mitchell (University of Birmingham) Measure theoretic entropy of random substitutions

Algorithms and complexity
Wednesday April 14, 2021, 10AM, Collège de France
Frédéric Magniez - Thomas Vidick (IRIF - California Institute of Technology) Cryptographie et communication quantiques

Deuxième cours de Frédéric Magniez au Collège de France sur les Algorithmes quantiques (à 10h), suivi d'un exposé de Thomas Vidick sur « Certifier la génération de nombres aléatoires avec le quantique » (à 11h30). Informations supplémentaires : https://www.college-de-france.fr/site/frederic-magniez/course-2021-04-14-10h00.htm

Automata
Friday April 16, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl
Arthur Jaquard A Complexity Approach to Tree Algebras: the Bounded Case

The talk is based on joint work with Thomas Colcombet. We initiate a study of the expressive power of tree algebras, and more generally infinitely sorted algebras, based on their asymptotic complexity.

Tree algebras in many of their forms, such as clones, hyperclones, operads, etc, as well as other kind of algebras, are infinitely sorted: the carrier is a multi sorted set indexed by a parameter that can be interpreted as the number of variables or hole types. Finite such algebras - meaning when all sorts are finite - can be classified depending on the asymptotic size of the carrier sets as function of the parameter, that we call the complexity of the algebra. This naturally defines the notions of algebras of bounded, linear, polynomial, exponential or doubly exponential complexity…

Our main result precisely characterizes the tree algebras of bounded complexity based on the languages that they recognize as Boolean closures of simple languages. Along the way, we prove that such algebras that are syntactic are exactly those in which, as soon as there are sufficiently many variables, the elements are invariant under permutation of the variables.

Semantics
Tuesday April 20, 2021, 10AM, 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
Tuesday April 20, 2021, 2:30PM, online
Ayreena Bakhtawar (La Trobe University) Metrical theory for the set of points associated with the generalized Jarnik-Besicovitch set