## 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, LinkedIn and Mastodon for our latest news:

## News

*27.5.2024*

Ahmed Bouajjani, Professor at IRIF, has been awarded for his contribution to research in the computer science field.
He has been nominated in the **Scientific Research category** for the 6th edition of the **“Trophées Marocains du Monde”**. Many congratulations!

*30.5.2024*

The **14th Île-de-France Programming Day** will take place on **Monday, June 10, 2024**, at Université Paris Cité, in the Department of Computer Science. This day is an opportunity for a **fun and friendly competition** between teams of **computer science undergraduate students** from Université Paris-Saclay, Université Paris Cité, and Sorbonne University. This day is jointly organized by Pierre Letouzey (IRIF), Jean-Baptiste Yunès (UPC), Emmanuel Chailloux (UPMC) and Jean-Christophe Filliâtre (Paris Saclay).

*10.4.2024*

IRIF is pleased to announce its second Distinguished Lecture of the year! Our invited speaker is **Omer Reingold**, professor of computer science at Stanford University and the director of the Simons Collaboration on the Theory of Algorithmic Fairness (Simons Foundation). **He will talk about Algorithmic Fairness**. Anyone interested is welcome to join us for this talk!

*12.4.2024*

The **rerun of Véronique Cortier Distinguished Talk** that was held on February is now available on the IRIF YouTube channel. Her subject was: **“Electronic voting: design and formal verification”**.

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

## Agenda

Non-permanent members' seminar

Thursday May 30, 2024, 4PM, Salle 3052 and Zoom Link

**Victor Arrial** *The Bang-Calculus: An Accessible Introduction to Subsuming Paradigms*

In this talk, we will present the Bang Calculus and provide multiple examples of (simple) properties that can be subsumed within this framework. Absolutely no prerequisites are required.

Higher categories, polygraphs and homotopy

Friday May 31, 2024, 2PM, Salle 3058

**Sacha Ikonicoff** *Catégories différentielles et tangentes pour les algèbres sur une opérade*

Dans cet exposé, nous décrirons une nouvelle notion de monade différentielle cartésienne. Cette structure consiste en une monade équipée d'une transformation naturelle appelée "combinateur différentiel". Pour une telle monade, nous montrerons que la catégorie (opposée) de Kleisli associée est munie d'une structure différentielle cartésienne, et que la catégorie d'algèbres associée est munie d'une structure tangente.

Finalement, nous considérerons l'exemple des algèbres sur une opérade. Nous montrerons que la monade associée à toute opérade (algébrique, symétrique) admet un combinateur différentiel. Nous étudierons la catégorie différentielle cartésienne et la catégorie tangente associée. Nous montrerons que cette catégorie tangente admet une structure tangente adjointe qui permet de retrouver certaines notions provenant de la géométrie algébrique et non-commutative.

Automata

Friday May 31, 2024, 2PM, Salle 3052

**Thomas Colcombet** *Bisimulation invariant MSO over finite transition systems*

Our proof techniques involve developing an algebraic theory of infinite regular trees, in particular establishing on the way that recognizable languages of regular trees coincide (over regular trees) with MSO definable language of trees.

Graph Transformation Theory and Applications

Friday May 31, 2024, 3PM, online

**Kristopher Brown** (Topos Institute, Berkeley, California, USA) *A graphical language for programming with graph rewriting*

Enumerative and analytic combinatorics

Tuesday June 4, 2024, 11AM, Salle 1007

**Pas De Séminaire (Mais Séminaire Flajolet Le Jeudi 6 Juin !)** *Pas de séminaire*

Algorithms and complexity

Tuesday June 4, 2024, 11AM, Salle 3052

**Kuo-Chin Chen** (Foxconn Research) *Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups*

Crucially, the walk operates on a state space encompassing both positively and negatively oriented simplices, effectively doubling its size compared to unoriented approaches. Through coherent interference of these paired simplices, we are able to successfully encode the combinatorial Laplacian, which would otherwise be impossible. This observation constitutes our major technical contribution. We also extend the framework by constructing variant quantum walks. These variants enable us to: (1) estimate the normalized persistent Betti numbers, capturing topological information throughout a deformation process, and (2) verify a specific QMA1-hard problem, showcasing potential applications in computational complexity theory.

Algorithms and complexity

Wednesday June 5, 2024, 11AM, Salle 4052 (PCQC)

**Marin Costes** (Université Paris-Saclay) *Space-time deterministic graph rewriting*

Non-permanent members' seminar

Thursday June 6, 2024, 4PM, Salle 3052

**Allen Ibiapina** *k-Linkage on Temporal Graphs*

Syntax Meets Semantics

Thursday June 6, 2024, 2PM, Salle 3071

**Adrienne Lancelot** (LIX Polytechnique and IRIF UPC) *Mirroring Call-by-Need, or Values Acting Silly*

We validate the design of the call-by-silly calculus via rewriting properties and multi types. In particular, we mirror the main theorem about call-by-need – that is, its operational equivalence with call-by-name – showing that call-by-silly and call-by-value induce the same contextual equivalence. This fact shows the blindness with respect to efficiency of call-by-value contextual equivalence. We also define a call-by-silly strategy and measure its length via tight multi types. Lastly, we prove that the call-by-silly strategy computes evaluation sequences of maximal length in the calculus.

Automata

Friday June 7, 2024, 2PM, Salle 3052

**Lê Thành Dũng (Tito) Nguyễn** *Computing the polynomial degree of size-to-height increase for macro tree transducers*