## 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

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

*23.11.2022*

**3 papers coauthored by IRIF members** will be presented at ITCS - Innovations in Theoretical Computer Science 2023.

*23.11.2022*

**Nicolas Behr** (IRIF) and **Paul-André Melliès** (IRIF) will speak at the CAP 22 conference which will take place at IHES on **Monday 28 and Tuesday 29 November**. The registration to the conference is free but mandatory.

*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*

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

*16.11.2022*

Les Assises des Mathématiques se déroulent à la Maison de l’Unesco du **14 au 16 novembre 2022**. **Valérie Berthé** et **Claire Mathieu**, deux membres de l’IRIF, sont intervenues respectivement à la **Table ronde sur la Synthèse nationale des Mathématiques** et à la **Table ronde sur les interactions entre les Mathématiques et les autres sciences**.

*7.11.2022*

The FRAIGNIAUD workshop (Fundamental Research and Algorithmic Innovations in Graphs, Networks and the Internet, with Applications and Upcoming Directions) will take place in Paris on the **28th and 29th of November**, on the occasion of Pierre FRAIGNIAUD’s 60th birthday.

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

## Agenda

Algorithmes et complexité

Mercredi 30 novembre 2022, 16 heures, Salle 3052

**Ce Jin** (MIT) *Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching*

We show that the complexity of LCS with threshold d smoothly interpolates between the two extreme cases up to n^{o(1)} factors: LCS with threshold d has a quantum algorithm in n^{2/3 + o(1)}/d^{1/6} query complexity and time complexity, and requires at least Omega(n^{2/3}/d^{1/6}) quantum query complexity.

Our result improves upon previous upper bounds O~(min{ n/d^{1/2}, n^{2/3} }) (Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin.

Our main technical contribution is a quantum speed-up of the powerful String Synchronizing Set technique introduced by Kempa and Kociumaka (STOC 2019). Our quantum string synchronizing set also yields a near-optimal LCE data structure in the quantum setting, and an algorithm for the k-mismatch matching problem with k^{3/4}n^{1/2+o(1)} quantum query complexity.

Based on a SODA'23 paper joint with Jakob Nogler (ETH Zurich) and a SODA'22 paper joint with Shyan Akmal (MIT).

Algorithmes et complexité

Mercredi 30 novembre 2022, 11 heures, Salle 3052

**Chris Brzuska** (Aalto University) *Obfuscation: Implications in Complexity and Cryptography*

Although iO seems such a weak definition, it turns out surprisingly powerful (*). It allows us to transform worst-case NP problems into one-way functions, one-way functions into public-key encryption and even into fully homomorphic encryption—transformations which otherwise suffer from (black-box) separations result. In fact, iO is so strong that its existence is mutually exclusive with other assumptions which had previously been considered plausible.

At the same time, iO is also very weak; it does not even imply that P is different from NP although most cryptographic primitives (one-way functions, public-key encryption etc.) do.

In this talk, we explore the above conceptual implications. The talk is intended for a (broad) theory audience.

(*) “I must admit that I was very skeptic of the possible applicability of the notion of indistinguishable obfuscation.” Oded Goldreich when commenting on the surprising success of iO in cryptographc research.

Combinatoire énumérative et analytique

Jeudi 1 décembre 2022, 14 heures, Salle 1007 et zoom

**Groupe De Lecture - Eva Philippe** (Eva Philippe (IMJ-PRG)) *Nu-Tamari lattice and Nu-associahedron*

Preuves, programmes et systèmes

Jeudi 1 décembre 2022, 10 heures 30, Salle 3052

**David Baelde** (ENS Rennes) *Logical foundations of the Squirrel prover*

Soutenances de thèses

Jeudi 1 décembre 2022, 14 heures, Salle 3052 du bâtiment Sophie Germain & Zoom

**Abhishek De** (IRIF) *Linear logic with least and greatest fixed points: truth semantics, complexity, and a parallel syntax*

Manuscript

Automates

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

**Léo Exibard** *Runtime monitoring for Hennessy-Milner logic with recursion over systems with data*

I then examine what kind of properties can be monitored at runtime, depending on the monitor model. A key aspect is that the logic has close links with register automata with non-deterministic reassignment, which yields a monitor synthesis algorithm, and allows to derive impossibility results. In particular, contrary to the regular case, restricting to deterministic monitors strictly reduces the set of monitorable properties.

This is joint work with the MoVeMnt team (Reykjavik University): Luca Aceto, Antonis Achilleos, Duncan Paul Attard, Adrian Francalanza, Karoliina Lehtinen.

Vérification

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

**Kohei Suenaga** (Kyoto University) *HELMHOLTZ: A Verifier for Tezos Smart Contracts Based on Refinement Types*

A smart contract is a program executed on a blockchain, based on which many cryptocurrencies are implemented, and is being used for automating transactions. Due to the large amount of money that smart contracts deal with, there is a surging demand for a method that can statically and formally verify them. This article describes our type-based static verification tool HELMHOLTZ for Michelson, which is a statically typed stack-based language for writing smart contracts that are executed on the blockchain platform Tezos. HELMHOLTZ is designed on top of our extension of Michelson's type system with refinement types. HELMHOLTZ takes a Michelson program annotated with a user-defined specification written in the form of a refinement type as input; it then typechecks the program against the specification based on the refinement type system, discharging the generated verification conditions with the SMT solver Z3. We briefly introduce our refinement type system for the core calculus Mini-Michelson of Michelson, which incorporates the characteristic features such as compound datatypes (e.g., lists and pairs), higher-order functions, and invocation of another contract. HELMHOLTZ successfully verifies several practical Michelson programs, including one that transfers money to an account and that checks a digital signature.

Algorithmes et complexité

Mardi 6 décembre 2022, 11 heures, Salle 1004

**Changpeng Shao** (University of Bristol) *Quantum communication complexity of linear regression*

Sémantique

Mardi 6 décembre 2022, 10 heures 30, Salle 1007

**Ariadne Si Suo** (University of Oxford) *Semiring Tensor and Iteration Theory*

A basic class of effects comes from the algebraic theory of modules for a semiring. The tensor of such theories is determined by the usually more tractable semiring tensor. I’ll give some examples, and then look at how the tensors work in languages with iteration. Our main contribution concerns an important class of subtheories of module theories. We observe that the subtheory tensor is also determined by the semiring tensor for several fundamental effects. I'll look at some examples of these subtheories and their tensors, and discuss how they support iteration via the underlying subsets.

This is my undergraduate summer project with Cristina Matache, Sean Moss, and Sam Staton.

One world numeration seminar

Mardi 6 décembre 2022, 14 heures, Online

**Christoph Bandt** (Universität Greifswald) *Automata generated topological spaces and self-affine tilings*