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

*22.1.2021*

IRIF is associated to two projects selected under the call “Émergence en Recherche” of Université de Paris: IDiLL, co-instigated by Michele Pagani with LIPN, and SPECTRANS by Jean-Baptiste Yunès with CLILLAC-ARP and LIPADE.

*22.1.2021*

French president Emmanuel Macron has presented a national plan for quantum technologies, including some aspects of quantum computing and communications. This is based on a parliamentary report co-written by Iordanis Kerenidis. More from CNRS including a special edition on the quantum revolution.

*15.1.2021*

V. Berthé (IRIF) & J. Barral spearhead the creation of 𝘎𝘋𝘙 **Multifractal analysis and self-similarity** as a renewal of `GDR Multifractal analysis' with a move towards symbolic dynamic systems.

*4.1.2021*

P. Fraigniaud (IRIF), F. Le Gall (Nagoya University), H. Nishimura (Nagoya University), and A. Paz (Universität Wien) will present at ITCS 2021 a quantum approach of distributed certification, for checking the consistency of large data sets replicated at several nodes of a network.

*5.1.2021*

Geoffroy Couteau (IRIF), Pooya Farshim (University of York), and Mohammad Mahmoody (University of Virginia) will present at ITCS 2021 a new framework for proving black-box separations in cryptography in a composable way.

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

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

## Events

Enumerative and analytic combinatorics

Wednesday January 27, 2021, 10:30AM, Virtuelle

**Franz Lehner** (TU Graz) *To be announced.*

Proofs, programs and systems

Thursday January 28, 2021, 10:30AM, Online

**Jérôme Feret** (INRIA) *Conservative approximation of systems of polymers*

The over-approximation of each derivative relies on symbolic reasoning. We use Kappa to describe our models. Kappa is a site-graph rewriting languages which is popular to describe protein-protein interaction networks. The main ingredients of Kappa, graph patterns, can be interpreted in two ways. Intensionally by the means of embeddings between graphs, or extensionally as the (potentially infinite) multi-sets of the complete graphs they occur in. This second interpretation leads to the definition of positive series of concentration of species. Interestingly, it can be proven that some universal constructions between graphs induce generic methods to prove the well-posedness of some numerical series, and some equality and inequality among them, hence providing a convenient tool-kit for symbolic reasoning

PhD defences

Thursday January 28, 2021, 3PM, Online

**Léonard Guetta** (IRIF) *Homology of strict omega-categories*

Automata

Friday January 29, 2021, 2:30PM, Salle 3052

**Stefan Göller** (University of Kassel) *Bisimulation Finiteness of Pushdown Systems Is Elementary*

Graph Transformation Theory and Applications

Friday January 29, 2021, 3PM, (online)

**Leen Lambers & Fernando Orejas** (Hasso-Plattner-Institut Potsdam, Germany & Technical University of Catalonia (UPC), Spain) *Confluence of Graph Transformation*

Traditionally, the set of critical pairs has been shown to constitute such a set. It is representative in the sense that for each conflict a critical pair exists, representing the conflict in a minimal context, such that it can be extended injectively to this conflict (M-completeness). Recently, it has been shown that initial conflicts constitute a considerably reduced subset of critical pairs, being still representative in a slightly different way. In particular, for each conflict there exists a unique initial conflict that can be extended (possibly non-injectively) to the given conflict (completeness). Compared to the set of critical pairs, the smaller set of initial conflicts allows for more efficient conflict as well as confluence analysis.

We continue by demonstrating that initial conflicts (critical pairs) are minimally complete (resp. minimally M-complete), and thus are both optimally reduced w.r.t. representing conflicts in a minimal context via general (resp. injective) extension morphisms. We proceed with showing that it is impossible to generalize this result to the case of rules with application conditions (equivalent to FOL on graphs). We therefore revert to a symbolic setting, where finiteness and minimal (M-)completeness can again be guaranteed. Finally, we describe important special cases (e.g. rules with negative application conditions), where we are able to obtain minimally complete (resp. M-complete) sets of conflicts in the concrete setting again.

Verification

Monday February 1, 2021, 11AM, BBB link

**François Schwarzentruber** (IRISA, ENS Rennes) *Connected multi-agent path finding*

Graphs

Tuesday February 2, 2021, 2PM, Salle 1007

**Zhouningxin Wang** *Density of $C_{-4}$-critical signed graphs*