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

## Welcome

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.

## Notion of the day

## News

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

## Events

Distributed algorithms and graphs

Tuesday April 13, 2021, 3PM, ZOOM

**Adrian Pastine** (Universidad Nacional de San Luis) *Null Decomposition of Graphs*

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*

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*

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*

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*