## Welcome

IRIF is a research laboratory of CNRS and Université Paris Cité, also hosting one Inria project-team.

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. Seven of its members have been distinguished by the European Research Council (ERC), six are members of the Institut Universitaire de France IUF), two are members of the Academia Europæa, and one is member of Académie des sciences.

## Notion of the day

## Social Networks

Follow us on Twitter/X and LinkedIn for our latest news:

## News

*30.1.2024*

How to design algorithms to analyze protocols in **electronic voting** ?
How to define mathematically **vote secrecy** ?
What is at stake ?
Read the interview Véronique Cortier granted us before her distinguished talk on 7 February, 2024.

*5.2.2024*

Join IRIF as **Financial Management Manager**! As part of an administrative team supervised by the Administrative Manager and consisting of 5 staff (including 3 managers under your responsibility), you will organise **tasks relating to the preparation, implementation and monitoring of financial operations**.
**Application deadline: Friday 23 February 2024**. | Planned start date: 1 March 2024

*29.1.2024*

**One full professor (professeur des universités)** and **two associate professor (maître de conference)** positions will open at IRIF.
**Fluency in French** is mandatory for these positions.
The application deadline is **March the 6th 2024** (16h00 - Paris time)

*1.2.2024*

We are delighted to welcome **David Saulpic**, **Research Fellow at the IRIF**. His favourite subject? **Algorithms**, and more specifically **clustering problems**. You can meet him in his office 4029A.

*31.1.2024*

**What kind of research policy?**
In an article for the french newspaper l'Humanité, Claire Mathieu explains the importance of **research** for France and the urgent need to make the field more **attractive** again, at the risk of **driving away young researchers**.

*2.1.2024*

Following the **adoption of the immigration law** by the government, Claire Mathieu **resigned from the Presidential Science Council**, which was set up on 7 December 2023.

*9.1.2024*

Congratulations to Pierre Fraigniaud, who won an Imre Simon Test-of-Time award 2024 for the paper "Collective Tree Exploration" with Leszek Gasieniec, Dariusz R. Kowalski, and Andrzej Pelc. It appeared in the proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004). It will be delivered at the 16th edition of LATIN, in Puerto Varas, Chile, March 18-22, 2024.

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

## Agenda

Verification

Monday February 26, 2024, 11AM, 3052 and Zoom link

**Loïc Germerie Guizouarn** (Université Paris-Est Créteil) *Quasi-synchronous communications and verification of distributed systems*

Formath

Monday February 26, 2024, 2PM, 3052

**Julien Narboux** (Université de Strasbourg) *Formalization of geometry, and automated theorem proving using constraint solving*

Enumerative and analytic combinatorics

Tuesday February 27, 2024, 11AM, Salle 1007

**Gilles Schaeffer** *From catalytic to algebraic decomposition, bijectively.*

Join work with Enrica Duchi

Algorithms and complexity

Tuesday February 27, 2024, 11AM, Salle 3052

**Sophie Huiberts** (LIMOS, Clermont-Ferrand) *Open problems about the simplex method*

Algorithms and complexity

Tuesday February 27, 2024, 2PM, Salle 3052

**Christian Konrad** (University of Bristol) *An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation*

We will focus on the two-pass setting, and we show that every randomized two-pass streaming algorithm that computes a better than 8/9-approximation to Maximum Matching requires strictly more than semi-streaming space.

Prior to our work, only a conditional two-pass lower bound by Assadi [SODA'22] was known that relates the quality of their lower bound to the maximum density of Ruzsa-Szemeredi graphs (RS-graphs) with matchings of linear sizes. In the best case, i.e., if very dense RS-graphs with linear-sized matchings exist, their lower bound rules out approximation ratios above 0.98, however, with current knowledge, only approximation factors of 1 − o(1) are ruled out.

Our lower bound makes use of the information cost trade-off of the Index problem in the two-party communication setting established by Jain et al. [JACM’09]. To the best of our knowledge, our work is the first that exploits this trade-off result in the context of lower bounds for multi-pass graph streaming algorithms.

Automata

Thursday February 29, 2024, 2PM, Salle 3052

**Ivan Varzinczak** *An Introduction to Defeasible Description Logics*

Speaker's short CV: Ivan Varzinczak is an associate professor at Université Paris 8. He holds a PhD (2006) in artificial intelligence from Université Paul Sabatier, France. Ivan has co-authored over 75 peer-reviewed publications on logic-based approaches to knowledge representation and reasoning in AI. In 2019 he defended his habilitation at Université d'Artois, France. Ivan is an associate editor of Artificial Intelligence and of the Journal of Artificial Intelligence Research and chairman of the steering committee of the International Workshop on Nonmonotonic Reasoning. In 2022, he served as program chair of the 12th International Symposium on Foundations of Information and Knowledge Systems (FoIKS). He has had several visiting researcher appointments and taught courses and tutorials worldwide, including two courses at ESSLLI and two tutorials at IJCAI.

Non-permanent members' seminar

Thursday February 29, 2024, 4PM, Salle 3052

**Huan Zhou** *Graph colouring: Extending brooks’ Theorem*

In this talk, I will introduce some basic conceptions and theorems of graph colouring, such as brooks’ Theorem. Moreover, I will introduce a new conception called k-truncated-degree choosability and some open problems.

Automata

Friday March 1, 2024, 2PM, Salle 3052

**Benjamin Bordais** *From Local to Global Optimality in Concurrent Parity Games*

This is a joint work with my former PhD advisors Patricia Bouyer and Stéphane Le Roux, and it is based on a paper published in CSL 2024.

Verification

Monday March 4, 2024, 11AM, 3052 and Zoom link

**Adrian Francalanza** (University of Malta) *To be announced.*

Formath

Monday March 4, 2024, 2PM, 3052

**Guillaume Baudart** *To be announced.*