## Welcome

IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and Université de Paris, 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. Six of its members have been distinguished by the European Research Council (ERC), five 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

## News

*18.1.2022*

**Two papers coauthored by IRIF members** will be presented at the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) held in Marseille, **March 15-18 2022**.

*25.11.2021*

Adrian Vladu's paper Faster Sparse Minimum Cost Flow by Electrical Flow Localization, jointly written with **Kyriakos Axiotis** and **Aleksander Madry**, will be presented at FOCS 2021.

*2.12.2021*

IRIF is very pleased to host for two months Serge Massar, Professor at the Université libre de Bruxelles (ULB) as part of the FSMP Distinguished Professor Fellowship. Serge Massar is the director of the Laboratoire d'Information Quantique (LIQ), of the Physics Department, Science Faculty, ULB. His research interests are **quantum information theory**, **experimental quantum** and **non linear optics**, **machine learning**.

*1.12.2021*

Prochaine conférence dans le cadre des **75 ans d’informatique** : *L’informatique dans le 7ème art : fiction ou réalité ?* Rendez-vous avec **Fabrice Kordon** le **jeudi 9 décembre-18h00** sur le campus Pierre et Marie Curie de Sorbonne Université (tour 25.26, 1er étage – salle 105).

*13.12.2021*

Delia Kesner (IRIF) will present her paper A Fine-Grained Computational Interpretation of Girard’s Intuitionistic Proof-Nets at **annual Symposium on Principles of Programming Languages**, POPL2022. The paper introduces a **functional term calculus** that captures the essence of the operational semantics of **Intuitionistic Linear Logic Proof-Nets** with a faithful degree of granularity, both statically and dynamically.

*17.12.2021*

Paul-André Melliès (IRIF), Arthur Vale, Zhong Shao, Jérémie Koenig (Yale) and Léo Stefanesco (MPI) will present a **layered concurrent object-based game semantics** for the purpose of compositional software specification and certification at **annual Symposium on Principles of Programming Languages**, POPL2022 : https://hal.inria.fr/hal-03456034.

*13.12.2021*

Jacques Sakarovitch (IRIF) was elected new IFIP Fellow. IFIP Fellow is the most **most prestigious IFIP's technical distinction** which is conferred by the **IFIP General Assembly** on a current or past member of an IFIP body in recognition of outstanding contributions in the field of information processing, in the role of a Technical Leader, Scientist, Engineer, or Educator.

*2.12.2021*

We are excited to be part of the “High-Performance Computer and Quantum Simulator hybrid” (HPCQS) aiming at creating a **world-class supercomputing ecosystem**. Learn more about the project here.

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

## Agenda

Enumerative and analytic combinatorics

Thursday January 20, 2022, 2PM, Salle 3052 et sur zoom

**Noémie Cartier** (Université de Paris-Saclay) *Lattice properties of acyclic pipe dreams*

Proofs, programs and systems

Thursday January 20, 2022, 10:15AM, Virtual room at link

**Bruno Dinis** (Universidade de Lisboa) *Functional interpretations and applications*

I will present several recent functional interpretations and some results that come from these interpretations. I will also give examples of application of functional interpretations, in the spirit of the proof mining program.

Automata

Friday January 21, 2022, 2:30PM, Salle 3052

**Victor Marsault** *Demonstration of Awali 2.1, a library for weighted automata and transducers.*

Awali may be accessed in C++ (awalidyn, or directly using templates) or in Python (awalipy). Awali can also be used interactively from its command-line interface (Cora) or using awalipy together with Jupyter, a top-level Python interpreter.

Awali may be downloaded from http://vaucanson-project.org/Awali/2.1/ and I'll be happy to address possible installation issues after the presentation.

Algorithms and complexity

Tuesday January 25, 2022, 2PM, 3052

**Simona Etinski** (INRIA / IRIF) *Latest challenges in post-quantum cryptography*

In this talk, we focus on the proposal for a digital signature. It is based upon a problem from coding theory, known as a syndrome decoding problem, and analyzed using cryptanalytic means. Namely, we analyze the time complexity of the information set decoding algorithms, widely believed to be the best algorithms for solving the syndrome decoding problem. By evaluating their complexity, both in the classical and quantum domain, we reason about the hardness of the problem. Finally, we give an example of the scheme based upon the syndrome decoding problem and analyze its security imposed by the hardness of the problem. We examine the tradeoff between signature's security and its size, which is a major challenge to be addressed in the competition.

One world numeration seminar

Tuesday January 25, 2022, 2:30PM, Online

**Claudio Bonanno** (Università di Pisa) *Infinite ergodic theory and a tree of rational pairs*

Enumerative and analytic combinatorics

Thursday January 27, 2022, 2PM, Salle 3052 et sur zoom

**Elba Garcia-Failde** (IMJ-PRG Sorbonne Universite) *TBD*

Proofs, programs and systems

Thursday January 27, 2022, 10:30AM, TBA

**Titouan Carette** (LORIA / Université de Lorraine) *To be announced.*

Graph Transformation Theory and Applications

Friday January 28, 2022, 3PM, online

**William Waites** (University of Strathclyde, Scotland, UK) *Rule-based Models of Epidemics*

Enumerative and analytic combinatorics

Thursday February 3, 2022, 2PM, Salle 1007

**Seminaire Flajolet** *d*

Automata

Friday February 4, 2022, 2:30PM, Salle 3052 (Online)

**Bartek Klin** *Orbit-finite-dimensional vector spaces, with applications to weighted register automata*

Applications of this include a decision procedure for equivalence of weighted register automata, which are the common generalization of weighted automata and register automata for infinite alphabets. The algorithm runs in exponential time, and in polynomial time for a fixed number of registers. As a special case, we can decide, with the same complexity, language equivalence for unambiguous register automata.

(Joint work with Mikołaj Bojańczyk and Joshua Moerman.)