## Bienvenue

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, qui héberge une équipe-projet Inria.

Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques.

L'IRIF regroupe près de deux cents personnes. Six de ses membres ont été lauréats de l'European Research Council (ERC), six sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences.

## Notion du jour

## Actualités

*6.12.2022*

We are happy to host **Lauren K. Williams** for a one-year visit at IRIF. To know more about her and her research, read her interview.

*30.11.2022*

**Sophie Laplante** (IRIF) and **Anupa Sunny** (IRIF) will present at ITCS 2023 their paper Certificate Games in which players are given inputs x, y such that f(x)\≠f(y). Their goal is to find a position where the bits of their inputs differ. This simple new game can be used to give bounds on query complexity, block sensitivity and several other complexity measures.

*25.11.2022*

Le prix informatique Lovelace-Babbage de l’Académie des Sciences 2023 récompense des scientifiques dont les travaux, des plus théoriques aux plus appliqués, contribuent à la **création des nouvelles technologies**. Date limite pour constituer son dossier de candidature : **10 décembre 2022.**

*18.11.2022*

On November 8th, **Iordanis Kerenidis (IRIF)** and 5 other founding members officially launched the EQSI-European Quantum Software Institute with a stakeholder event in Paris. This initiative aims to further align development processes and jointly achieve responsible innovation in Europe for **Quantum Software** and **Quantum Algorithms**, through co-creation with industry and Quantum Hardware partners.

*14.11.2022*

Congratulations to **Olivier Carton (IRIF)**, head of the pole Automata, structures and verification at IRIF and recently **appointed senior member of Institut universitaire de France (IUF)**. He is interested by the links and connexions between normality and automata.

*14.11.2022*

Lucas Pesenti and **Adrian Vladu (IRIF)** will present, at SODA 2023, their paper Discrepancy Minimization via Regularization. They make progress towards conjectures in discrepancy theory by showing that Newton's method can produce low discrepancy colorings.

*14.11.2022*

**Guillaume Chapuy (IRIF)** and Guillem Perarnau (Universitat Politècnica de Catalunya) will present, at SODA 2023, their paper proving that almost all automata with n states have a reset word not much longer than √n. This is based on a structure result saying that almost all automata are w-trees (i.e., the w-transitions induce a tree), for some very short word w — whose length is only logarithmic.

*18.11.2022*

Le Hcéres a publié la synthèse nationale et de prospective sur les mathématiques. Cette synthèse est constituée de **trois volumes** fruit d’un travail inédit mené pendant 2 ans par le comité d’experts dont fait partie **Valérie Berthé (IRIF).** Volume 1 : Rapport principal. Volume 2 : Analyse disciplinaire et des interactions scientifiques. Volume 3 : Caractérisation des publications dans le monde et en France.

(Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.)

## Agenda

Combinatoire énumérative et analytique

Jeudi 8 décembre 2022, 14 heures, Salle 3052 et zoom

**Amanda Burcroff** (Harvard) *Dyck Path Expansion Formulas for Rank 2 Cluster Algebras*

Preuves, programmes et systèmes

Jeudi 8 décembre 2022, 10 heures 30, Salle 3052 & online (Zoom link)

**Beniamino Accattoli** (INRIA Saclay, PARTOUT Project-Team) *Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic.*

Séminaire des doctorants

Jeudi 8 décembre 2022, 16 heures, 3052 and Zoom link

**Srinidhi N** *Domain specific language for Testing consensus implementations*

No prior knowledge of distributed systems/algorithms is required.

Catégories supérieures, polygraphes et homotopie

Vendredi 9 décembre 2022, 14 heures, Salle 1007

**Manuel Araujo** (Cambridge University) *String diagrams for n-sesquicategories*

https://arxiv.org/abs/2202.09293 ; https://arxiv.org/abs/2210.07704

Automates

Vendredi 9 décembre 2022, 14 heures, Salle 3052

**Sarah Winter** *A Regular and Complete Notion of Delay for Streaming String Transducers*

We show that our notion is regular: we design a finite automaton that can check whether the delay between any two SSTs executions is smaller than some given bound. As a consequence, our notion enjoys good decidability properties: in particular, while equivalence between non-deterministic SSTs is undecidable, we show that equivalence up to fixed delay is decidable. Moreover, we show that our notion has good completeness properties: we prove that two SSTs are equivalent if and only if they are equivalent up to some (computable) bounded delay.

Together with the regularity of our delay notion, it provides an alternative proof that SSTs equivalence is decidable. Finally, the definition of our delay notion is machine-independent, as it only depends on the origin semantics of SSTs. As a corollary, the completeness result also holds for equivalent machine models such as deterministic two-way transducers, or MSO transducers.

This is joint work with Emmanuel Filiot, Ismaël Jecker, and Christof Löding.

Vérification

Lundi 12 décembre 2022, 11 heures, 1007 and Zoom link

**Salim Chouai** (Mohammed VI University) *Synthesis of Accuracy Specification under Differential Privacy*

One world numeration seminar

Mardi 13 décembre 2022, 14 heures, Online

**Hiroki Takahasi** (Keio University) *Distribution of cycles for one-dimensional random dynamical systems*

This talk is based on the preprint arXiv:2108.05522. If time permits, I will mention some future perspectives in this project.

Algorithmes et complexité

Mercredi 14 décembre 2022, 11 heures, Salle 3052

**Fabien Dufoulon** (University of Houston) *Sleeping is Superefficient: MIS in Exponentially Better Awake Complexity*

Energy is a premium resource in battery-powered wireless and sensor networks, and the bulk of it is used by nodes when they are awake, i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping, it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake, also called the awake complexity. An intriguing question is whether one can design a distributed MIS algorithm that is significantly more energy-efficient (having very small awake complexity) compared to existing algorithms.

Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of O(log n) and also bypassing its fundamental Ω(√(log(n)/log(log n))) round complexity lower bound (almost) exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in O(log log n) awake complexity with high probability. Since a node spends significant energy only in its awake rounds, our result shows that MIS can be computed in a highly energy-efficient way compared to the existing MIS algorithms.

Algorithmes et complexité

Mercredi 14 décembre 2022, 14 heures, Salle 3052

**Hang Zhou** (École Polytechnique) *Unsplittable Euclidean Capacitated Vehicle Routing*

Our main result is a polynomial-time $(2+\epsilon)$-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].

This is joint work with Claire Mathieu and Fabrizio Grandoni.

Théorie des types et réalisabilité

Mercredi 14 décembre 2022, 14 heures, Salle 1007

**Rémy Cerda** (Institut de Mathématiques de Marseille, Université Aix-Marseille) *Non encore annoncé.*