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.

Constantin Enea

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.

Ahmed Bouajjani

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.

Miklos Santha and Troy Lee

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.

Mahsa Shirmohammad

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.

Jean-Éric Pin

7.10.2018
Jean-Eric Pin, CNRS senior researcher at IRIF, is awarded the Arto Salomaa prize for his outstanding contribution to the field of Automata Theory.

QIP19

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.

SODA19

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.

ITCS19

21.11.2018
Two papers coauthored by IRIF members will be presented at ITCS’19, a prestigious conference to promote research that carries a strong and innovative conceptual message in TCS. Topics include communication complexity and quantum dueling algorithms.

Preuves, programmes et systèmes
jeudi 13 décembre 2018, 10h30, ENS Lyon
Journée Chocola () ENS Lyon

Automates
vendredi 14 décembre 2018, 14h30, Salle 3052
Colin Riba (École Normale Supérieure de Lyon) tba

tba

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