## 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

(Ordonnées par priorité et aléatoire)

*15.2.2019*

**Fabian Reiter** wrote a short popularisation article in the Blog Binaire
of the newspaper Le Monde. This article explains (in French) some
aspects of his PhD thesis, recently awarded the Honorable Mention of
the Gilles Kahn prize.

*15.2.2019*

In collaboration with **Yoav Rodeh** (Weizmann Institute of Science),
**Pierre Fraigniaud** and **Amos Korman** from IRIF published a paper in the Journal of the ACM entitled “Parallel Bayesian Search with no
Coordination”.

*19.2.2019*

Amaury Pouly (IRIF) with François Fages, **Guillaume Le Guludec**
and Olivier Bournez were awarded the prize "La Recherche": they have
shown that chemical reactions, as the ones taking place in cells, can
simulate Turing machines. Chemical reactions are universal computers.

*17.1.2019*

Pierre Fraigniaud from IRIF organizes the Workshop Complexity and Algorithms (CoA), in the framework of GdR IM, Roscoff, France, **April 1-5, 2019**. The objective of this workshop is to gather the French community on design and analysis of algorithms, of all forms.
**Deadlines**: submission by 01/02/2019, registration by 02/03/2019.

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

*1.2.2019*

IRIF has the great pleasure to welcome **Uri Zwick**, professor at the Blavantik School of Computer Sience (University of Tel-Aviv), who is visiting for four months. His stay is financed by an FSMP chair. Uri is an expert in algorithms, data structures and games. Meet him in office 4048.

*8.1.2019*

IRIF has the great pleasure to welcome a new researcher (CNRS), Amaury Pouly, an expert in continuous models of computations, and the analysis and verification of continuous/hybrid dynamical systems.

*23.1.2019*

FILOFOCS (French-Israeli Laboratory on Foundations of Computer Science),
the first International Joint Unit in Israel, was just created by CNRS, Univ. Paris Diderot, Tel-Aviv Univ.,
Hebrew Univ. of Jerusalem and Weizmann Institute. IRIF hosts its “mirror site” in France, and
Adi Rosén from IRIF is deputy director.

## Événements

Combinatoire énumérative et analytique

Mardi 19 février 2019, 11 heures, Salle 3052

**Danupon Nanongkai** (KTH) *Distributed Shortest Paths, Exactly*

Algorithmes et complexité

Mardi 19 février 2019, 11 heures, Salle 3052

**Danupon Nanongkai** (KTH) *Distributed Shortest Paths, Exactly*

Systèmes complexes

Mardi 19 février 2019, 11 heures, Salle 3052

**Danupon Nanongkai** (KTH) *Distributed Shortest Paths, Exactly*

Graphes

Mardi 19 février 2019, 14 heures, Salle 1007

**Marthe Bonamy** (CNRS - LABRI) *Around Brooks' theorem*

Graphes

Mardi 19 février 2019, 11 heures, Salle 3052

**Danupon Nanongkai** (KTH) *Distributed Shortest Paths, Exactly*

Exposés hors-séries

Mercredi 20 février 2019, 13 heures, Salle 3052

**Giulio Manzonetto** (LIPN) *A syntactic and semantic analysis of program equivalences*

Preuves, programmes et systèmes

Jeudi 21 février 2019, 10 heures 30, Salle 3052

**Damiano Mazza** (CNRS) *Intersection Types and Runtime Errors in the Pi-Calculus*

Joint work with Ugo Dal Lago, Marc De Visme, Akira Yoshimizu

Exposés hors-séries

Jeudi 21 février 2019, 13 heures, Salle 3052

**Pablo Arrighi** (Aix-Marseille Université) *Quantum, automata, computability and universality*

Exposés hors-séries

Jeudi 21 février 2019, 11 heures 45, Salle 1007

**Samule Giraudo** (Université Paris-Est Marne-la-Vallée) *Graded graphs and operads*

Gâteau de l'IRIF

Jeudi 21 février 2019, 17 heures 30, in front of room 3052

**Isaac Konan, Mahsa Shirmohammadi** (IRIF Cake^{TM}) *Gâteau de l'IRIF*

^{TM}is an amazing opportunity to meet people while simultaneously eating cakes baked by your fellow colleagues! Join us every Thursday, at 5pm, in front of room 3052 (Sophie Germain 3rd floor) for a weekly feast. You can also express your cooking skills and volunteer to bake a cake by sending an email to cake@irif.fr.

Catégories supérieures, polygraphes et homotopie

Vendredi 22 février 2019, 14 heures, Salle 1007

**Cédric Ho Thanh** (IRIF) *The equivalence between many-to-one polygraphs and opetopic sets*

Automates

Vendredi 22 février 2019, 14 heures 30, Salle 3052

**Georg Zetzsche** (MPI) *Non encore annoncé.*

Vérification

Lundi 25 février 2019, 11 heures, Salle 1007

**Pierre Courtieu** (CNAM) *A proof framework for mobile robots protocols*

We present a framework, named Pactole, for designing distributed protocols for mobile robots, stating properties about these protocols and proving these properties. We can also prove *impossibility statement* i.e. that there exists no protocol achieving some property.

Our technique cannot be compared to but can be seen as complementary to model checking in the sense that our proofs are not automated but allow for instance to conclude that a protocol is correct *for any* starting configuration, number of robots, that is not proven impossible.

Algorithmes et complexité

Mardi 26 février 2019, 11 heures, Salle 1007

**Uri Zwick** (Tel Aviv University) *Faster k-SAT algorithms using biased-PPSZ*

Joint work with Thomas Dueholm Hansen, Haim Kaplan and Or Zamir