## Bienvenue à l'IRIF

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris-Diderot, 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), trois sont membres de l'Institut Universitaire de France (IUF) et deux sont membres de l'Academia Europæa.

## Notion du jour

## Actualités

*9.12.2018*

The Alexander von Humboldt Foundation has honored Ahmed Bouajjani (IRIF) with the prestigious **Carl Friedrich von Siemens Research Award**, in recognition of his research contributions.

*13.12.2018*

Constantin Enea (IRIF) will present at POPL 2019 a methodology for specifying software modules whose operations satisfy multiple consistency levels. This work has revealed previously unknown documentation errors and bugs in Java concurrent objects.

*19.11.2018*

IRIF has the great pleasure to welcome **Mahsa Shirmohammadi**, researcher scientist (CNRS) from LIS, who is visiting IRIF for six months and who is an expert in the analysis and verification of timed, counter and probabilistic systems.

*3.12.2018*

Maybe you are an eager bitcoin miner? Maybe you are a fan of quantum computing too, and you wonder what will change in the mining competition when done by quantum computers? Find some answers in a paper coauthored by Miklos Santha (IRIF) to be presented at ITCS’19.

*5.11.2018*

Amélie Gheerbrand and Cristina Sirangelo from IRIF co-organize with L. Libkin, L. Segoufin, and P. Senellart, the *2019 Spring School on Theoretical Computer Science* (**EPIT**) on *Databases, Logic and Automata*, to happen the **7-12 April 2019** in Marseille. Preregistration before **13 January 2019**.

*17.11.2018*

Four papers coauthored by IRIF members will be presented at POPL’19, the main conference on programming languages and programming systems. The papers' topics are game semantics, proof theory, gradual typing, and consistency for concurrent computations.

**Games**are mathematical objects used for modeling situations in which several participants/players interact, and each of them aims at fulfilling a personal goal. Real games such as chess or go are cases in which there are two players which are opponent. Games occur in computer science for modeling the logical duality between conjunction and disjunctions, or for defining particular families of complexity classes. Games appear in verification for describing how a system has to react to the environment (the opponent) in order to perform what it has been designed for.

**Gradual typing**is a technique that allows the programmer to control which parts of a program check their type correctness (i.e., that apples are added to apples) before execution and which parts check it during their execution instead. It is often used to

*gradually*add the before-execution check to dynamic languages, like JavaScript, which perform the check only at run-time, since it is generally better to find errors before the execution of a program rather than during its execution.

**Proof theory**is the branch of mathematical logic that studies proofs as mathematical objects. In particular, proof are syntactic constructions built from axioms and inference rules. Relevant to computer science are the studies of computational and complexity aspects of proofs.

**Memory consistency models**characterize the effect of concurrent invocations to a library implementing a shared state, e.g., a queue or a key-value map. Strong consistency means that the results of concurrently-executed invocations match the results of some serial execution of those same invocations. Since strong consistency carries a significant penalty on performance, modern implementations provide weaker guarantees known as weak consistency models, e.g., eventual or causal consistency.

*20.11.2018*

One paper coauthored by Laurent Feuilloley while he was PhD student at IRIF will be presented at SODA’19, the main conference in algorithm design. The paper provides lower bounds for the fundamental problem of text indexing with mismatches and differences using the Strong Exponential Time Hypothesis.

*20.11.2018*

Two papers coauthored by IRIF members will be presented at QIP’19, the main conference for theoretical quantum information research. Topics include efficient quantum algorithms for both algebraic and distributed problems.

## Événements

Automates

vendredi 14 décembre 2018, 14h30, Salle 3052

**Colin Riba** (École Normale Supérieure de Lyon) *A Curry-Howard approach to tree automata*

Rabin's Tree Theorem proceeds by effective translations of MSO-formulae to tree automata. We show that the operations on automata used in these translations can be organized in a deduction system based on intuitionistic linear logic (ILL). We propose a computational interpretation of this deduction system along the lines of the Curry-Howard proofs-as-programs correspondence. This interpretation, relying on the usual technology of game semantics, maps proofs to strategies in categories of two-player games generalizing the usual acceptance games of tree automata.

Catégories supérieures, polygraphes et homotopie

vendredi 14 décembre 2018, 14h00, Salle 1007

**Cameron Calk** (ENS Lyon) *L'homotopie dirigée et l'inversion temporelle*

Graphes

mardi 18 décembre 2018, 15h30, Salle 3052

**Bergougnoux Benjamin** (IRIF) *Rank Based Approach on Graphs with Structured Neighborhood*

In this talk, I will present a framework combining the rank-based approach with the notion of $d$-neighbor equivalence. The rank-based approach is a technique introduced by Bodlaender et al. in 2015 to obtained $2^{O(k)}\cdot n$ time algorithms, $k$ the treewidth of the input graph, for a wide range of connectivity problems.

The $d$-neighbor equivalence is a tools introduced by Bui-Xuan et al. in 2013 to obtained efficient parameterized algorithms for many width measures (clique-width, rank-width, mim-width,…) and for many problems with a locally checkable constraint (Dominating Set, Independent Set,…).

By combining these two notions, we obtain efficient algorithms for several connectivity problems such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. For all these problems, we obtain $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ time algorithms parameterized respectively by clique-width, $\mathbb{Q}$-rank-width, rank-width and maximum induced matching width. Our approach simplifies and unifies the known algorithms for each of the parameters and match asymptotically also the best time complexity for Vertex Cover and Dominating Set.

Paper available on HAL : https://hal.archives-ouvertes.fr/hal-01799573v2/document

Combinatoire énumérative et analytique

jeudi 20 décembre 2018, 11h45, Salle 1007

**Cyrille Chenavier** (INRIA (Lille)) *Quotients of the magmatic operad: lattice structures and convergent rewrite systems*

Automates

vendredi 21 décembre 2018, 14h30, Salle 3052

**Jérôme Leroux** (LaBRI) *The Reachability Problem for Petri Nets is Not Elementary*

Petri nets, also known as vector addition systems, are a long established and widely used model of concurrent processes. The complexity of their reachability problem is one of the most prominent open questions in the theory of verification. That the reachability problem is decidable was established by Mayr in his seminal STOC 1981 work, and the currently best upper bound is non-primitive recursive cubic-Ackermannian of Leroux and Schmitz from LICS 2015. We show that the reachability problem is not elementary. Until this work, the best lower bound has been exponential space, due to Lipton in 1976.

Joint work with Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Filip Mazowiecki.