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

IRIF has the great pleasure to welcome a new researcher (INRIA ISFP): Guillaume Baudart, an expert in on probabilistic and reactive programming languages (language design, semantics, static analysis, compilation, inference).

*23.11.2023*

IRIF has the great pleasure to welcome a new researcher (INRIA): Gabriel Scherer, an expert in programming languages, with theoretical aspects of type systems, programming language implementation, general programming language concepts, and even some syntactic aspects.

*24.11.2023*

Sylvain Perifel will **defend his habilitation to direct research [HDR]** on Monday **4 December 2022 at 2pm** in the Pierre-Gilles de Gennes Amphitheatre of the Condorcet building. His subject is *L'aléatoire par le prisme des polynômes et de la compression*.

*21.11.2023*

Du mardi 28 novembre au jeudi 30 novembre, nous recevrons à l'IRIF le comité d'évaluation de l'HCERES dans le cadre de l'évaluation de notre laboratoire. Programme

*14.11.2023*

We are very proud to announce that two papers by two IRIF researchers have been selected for the SODA conference! Congratulations to François Sellier and Robin Vacus.

*7.11.2023*

We are very proud to announce that four papers by six IRIF researchers have been selected for the POPL conference!
Congratulations to Claudia Faggian and Gabriele Vanoni, Mahsa Shirmohammadi, Giuseppe Castagna, Mickaël Laurent and Gabriel Scherer.

*16.11.2023*

La prochaine édition de **Mathématiques en mouvement**, conférence proposée par la FSMP, aura pour thème *Des preuves et des programmes*. Organisée sous la houlette de Hugo Herbelin, elle aura lieu le **samedi 2 décembre** 2023 de 14h à 18h.

*10.10.2023*

We are very proud to announce that five papers by six IRIF researchers have been selected for the CSL conference! Congratulations to Quentin Aristote, Guillaume Geoffroy, Roman Kniazev, Jérémy Ledent, François Laroussinie and Vincent Moreau.

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

## Agenda

Algorithms and complexity

Tuesday December 5, 2023, 11AM, Salle 3052

**Marc-Olivier Renou** (INRIA Saclay) *Causal and No Signalling-LOCAL models as the largest generalization of synchronous quantum distributed computing*

Finding lower bounds on the maximal speed at which QIT can solve a task is tricky. To circumvent this difficulty, several proofs based on the No-Signalling (NS) Principle (which states that an event A can influence an event B only if some signal can physically be sent from A to B) were proposed and a new NS-LOCAL model of distributed computing was proposed.

I’ll re-interpret this NS-LOCAL model based on the theoretical physics formalism of light cones in circuits. I will justify that the NS-LOCAL model is the “largest reasonable model with a pre-shared resource between the nodes”. Then, I’ll introduce a weaker Causal-LOCAL model, the “largest reasonable model without pre-shared resource between the nodes”.

All this will be illustrated with easy to understand examples. I was recently told by Vaclav Rozhon: We computer scientists are very scared of the word “quantum”. Note that I’ll almost not talk about quantum theory, hence no need to be scared.

Enumerative and analytic combinatorics

Thursday December 7, 2023, 10AM, IHP

**Séminaire Flajolet Et Conférence Ihp:** *Computer Algebra For Functional Equations In Combinatorics And Physics Du 4 Au 8 Décembre.*

Inscription obligatoire sur le site de la conférence: https://indico.math.cnrs.fr/event/8115/registrations/

Voir aussi: https://semflajolet.math.cnrs.fr/

Proofs, programs and systems

Thursday December 7, 2023, 10:30AM, Salle 3052 & online (Zoom link)

**Meven Lennon-Bertrand** (Université de Cambridge) *Towards a certified proof assistant kernel – What it takes and what we have*

Non-permanent members' seminar

Thursday December 7, 2023, 4PM, Salle 3052

**Esaie Bauer** *Proof theory in Multiplicative-Additive Linear Logic*

Syntax Meets Semantics

Thursday December 7, 2023, 2PM, Salle 3052

**Pablo Barenbaum** (Universidad Buenos Aires) *Sharing in linear logic and call-by-need*

Automata

Friday December 8, 2023, 2PM, Salle 3052

**Anantha Padmanabha** *Consistent Query Answering under Primary Keys*

The conjecture is open in general and has been open for more than two decades. In this talk we will introduce two new algorithms that we have devised, one based on fix-point computation and the other based on bipartite matching. We will also see how these algorithms can be used to prove the dichotomy for the cases that were previously open.

These results were obtained in collaboration with Diego Figueira, Luc Segoufin and Cristina Sirangelo and combine the results that were presented at ICDT 2023 and what will be presented at PODS 2024.

Distributed algorithms and graphs

Friday December 8, 2023, 3PM, 1007

**Pierre Aboulker** (ENS-Paris) *Clique number of tournaments*

Verification

Monday December 11, 2023, 11AM, 3052 and Zoom link

**Sarah Winter** (IRIF) *To be announced.*

Enumerative and analytic combinatorics

Tuesday December 12, 2023, 11AM, Salle 1007

**Philippe Nadeau** *To be announced.*

Algorithms and complexity

Tuesday December 12, 2023, 11AM, Salle 3052

**Deeksha Adil** (ETH Zurich) *Dynamically Computing Approximate Eigenvectors*

This is based on a very recent work with Thatchaphol Sararunak.