## Welcome to IRIF

IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and université Paris-Diderot, also hosting two INRIA project-teams.

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), and two are members of the Academia Europæa.

## Notion of the day

## News

*8.10.2019*

Researchers of IRIF are participating in the “Fête de la Science”! Meet them at the University of Paris **this week** to better understand the first principles of computing!

*10.9.2019*

IRIF is seeking excellent candidates for about **10 postdoctoral positions** in all areas of the Foundations of Computer Science. Deadline for applications: **Nov. 3, 2019**.

*8.10.2019*

From ancient history to quantum, learn about cryptography at “Fête de la science” in an entertaining talk by Sylvain Perifel (IRIF) **Friday October 11th, 11am**
at Amphitheater 4C, Halle aux farines.

*8.10.2019*

The SODA 2020 conference will include a paper by Vincent Cohen-Addad (LIP6), Frederick Mallmann-Trenn (King's College) and Claire Mathieu (IRIF) about computing with noisy data. The problem: select valuable objects in a setting where each assessment has a probability of error, using redundant assessments.

*23.9.2019*

Giuseppe Castagna (IRIF) and Jeremy Siek (Indiana) organize WGT 2020, the first *ACM SIGPLAN Workshop on Gradual Typing*, colocated with POPL. Submission deadline: Monday, October the 21st.

*1.10.2019*

IRIF has the great pleasure to welcome a **new research scientist** (CNRS): **Geoffroy Couteau**, an expert in cryptography, with a focus on secure computation protocols and zero-knowledge proofs.

*2.10.2019*

IRIF has the great pleasure to welcome a **new associate professor** (Université de Paris): Hugo Férée, an expert in various aspects of complexity theory, with interests in programming languages and formal proofs.

*25.9.2019*

**Three papers** coauthored by IRIF members will be presented at SODA’20, the main conference in algorithm design. Topics include the study of noisy models, aggregate rankings, and graph diameters.

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

## Events

Verification

Monday October 14, 2019, 11AM, Salle 1007

**Laurent Doyen** (LSV, ENS Paris-Saclay) *Expected Finite Horizon*

A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon T, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping time distribution with expected stopping time T, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping time distribution can be achieved in polynomial time. Consequently, our polynomial-time algorithm for adversarial stopping time also computes an optimal plan among all possible plans.

Algorithms and complexity

Tuesday October 15, 2019, 11AM, Salle 1007

**Zvi Lotker** (Ben Gurion University) *Variation on preferential-attachment*

Enumerative and analytic combinatorics

Thursday October 17, 2019, 2PM, Salle 1007

**Mark Skandera** (Lehigh university) *To be announced.*

Proofs, programs and systems

Thursday October 17, 2019, 10:30AM, École normale supérieure de Lyon

**Eric Finster** *Séminaire Chocola*

Higher categories, polygraphs and homotopy

Friday October 18, 2019, 2PM, Salle 1007

**Léonard Guetta** (IRIF) *Colimites homotopiques et tranches*