## Welcome to IRIF

IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and Université de Paris, 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

*13.1.2020*

Iordanis Kerenidis, CNRS senior researcher (IRIF) and director
of the Paris Centre for Quantum Computing, is one of the three authors
of the report about Quantum Technologies requested by the French
government.

*15.1.2020*

IRIF has the great pleasure to welcome a **new starting researcher**
(Inria): Emilio J. Gallego Arias, an expert in interactive theorem proving and the Coq proof assistant.

*7.1.2020*

Guillaume Ducoffe (Bucarest Univ. and ICI) will present at SODA’20 a result obtained with Michel Habib (IRIF) and Laurent Viennot (IRIF and Inria) showing that diameter can be computed in truly sub-quadratic time in any H-minor free graph. This extends a recent breakthrough on planar graphs.

*7.1.2020*

Claire Mathieu and Simon Mauras (IRIF) will present at SODA’20 several approximation algorithms for top-list aggregation, an optimization problem from the field of information retrieval: compute the output full-ranking which is closest to a collection of input top-lists.

*6.1.2020*

We are delighted to host as part of our IRIF Distinguished Talks Series **Martin Grohe** (RWTH Aachen University) on **Friday January 24, 2020, 10:30am** for a talk entitled “Symmetry and Similarity”.

*10.1.2020*

Université de Paris has opened **one permanent associate professor** position in Computer Science. Recruited researcher will join IRIF.

*10.1.2020*

IRIF has the great pleasure to welcome a **new research scientist** (CNRS): **Matthieu Josuat-Vergès**, an expert in enumerative combinatorics and algebraic combinatorics.

*23.12.2019*

IRIF is proud to announce that Claire Mathieu, senior research scientist at IRIF, has been elected at the **Académie des sciences** for the section of mechanical engineering and computer science.

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

## Events

Algorithms and complexity

Tuesday January 21, 2020, 11AM, Salle 1007

**Tatiana Starikovskaya** (ENS) *Sliding window property testing for regular languages*

In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject it if it is far from the language. We consider deterministic and randomized sliding window property testers with one-sided and two-sided errors. In particular, we show that for any regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.

The talk is based on a joint work with Ganardi, Hucke, and Lohrey published in ISAAC 2019.

Semantics

Wednesday January 22, 2020, 10:30AM, Salle 3014

**John Bourke** (Masaryk University (Brno)) *Weak adjoint functor theorems and accessible infinity-cosmoi*

Enumerative and analytic combinatorics

Thursday January 23, 2020, 2PM, Salle 1007

**Sergey Dovgal** (Université Paris 13) *The critical point of phase transition in random objects*

Proofs, programs and systems

Thursday January 23, 2020, 10:30AM, Salle 3052

**Robert Atkey** (University of Strathclyde) *To be announced.*

Algorithms and complexity

Thursday January 23, 2020, 11AM, Salle 1007

**Moni Naor** (Weizmann Institute) *Instance Complexity and Unlabeled Certificates in the Decision Tree Model*

In this talk I will discuss labeled and unlabeled certificates, in particular in the context of ``instance optimality“. This is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively.

Joint work with Tomer Grossman and Ilan Komargodski

Algorithms and discrete structures

Thursday January 23, 2020, 11AM, Salle 1007

**Moni Naor** (Weizmann Institute) *Instance Complexity and Unlabeled Certificates in the Decision Tree Model*

In this talk I will discuss labeled and unlabeled certificates, in particular in the context of ``instance optimality”. This is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively.

Joint work with Tomer Grossman and Ilan Komargodski

IRIF seminar

Friday January 24, 2020, 10:30AM, Amphi Buffon

**Martin Grohe** (RWTH Aachen University) **IRIF Distinguished Talks Series**: Symmetry and Similarity

One of the earliest applications of isomorphism testing was in chemistry, more precisely chemical information systems. Today, applications of isomorphism testing and symmetry detection are ubiquitous in computing. Prominent examples appear in optimisation, malware detection, and machine learning. However, in many of these applications, we only need to decide if two structures are sufficiently similar, rather than exactly the same. It turns out that determining how similar two structures are is an even harder computational problem than deciding whether they are isomorphic.

My talk will be an introduction to algorithmic aspects of symmetry and similarity, ranging from the fundamental complexity theoretic “Graph Isomorphism Problem” to applications in optimisation and machine learning.

Higher categories, polygraphs and homotopy

Friday January 24, 2020, 2PM, Salle 1007

**Sebastian Posur** (Universität Siegen) *Methods of constructive category theory*

Automata

Friday January 24, 2020, 2:30PM, Salle 3052

**Olivier Bournez** (LIX) *Caractérisation de classes de complexité et calculabilité avec des équations différentielles.*