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

## News

*25.1.2023*

**Claire Mathieu**, membre de l’IRIF et **spécialiste des algorithmes**, est intervenue à l’émission Arrêt sur Images autour du ChatGPT. Comment cette IA construit-elle ses textes ? Pourquoi parvient-elle à couvrir à peu près n’importe quel sujet ?

*27.1.2023*

A **full-time research associates position** is available to work on the **VeSyAm research project**. The position will start in **July 2023**. Deadline to apply: **12 noon on 15 Feb 2023**. Further information in the job description.

*16.1.2023*

**Claire Mathieu** and 8 other authors co-authored the article "Découpage électoral des circonscriptions législatives en France : Déséquilibres démographiques et contraintes territoriales" about a **new perspective for understanding electoral maps**, using **computational social science** to study the criteria which shape how electoral districts are drawn up in France.

*13.1.2023*

**Internship proposal** for Masters student in computer science at LS2N and IRIF in Real-time analysis and verification of ROS2 robotic applications. To apply, please refer to the internship description.

*11.1.2023*

LAFI'23, a workshop affiliated to POPL’23 about **Languages for Inference**, will be held on **January 15, 2023**, as a bi-located event in Boston and at Université Paris Cité. The Paris antenna will take place in salle Leduc, at the first floor of Saints-Pères building, 45 rue des Saints-Pères, 75006 Paris, from 3pm to 9:30pm Paris time. The The talks of V. Blanchi, G. Caylak, M. Pagani (IRIF), F. Zaiser will happen physically in Paris. Registration is mandatory.

*14.12.2022*

**Ahmed Bouajjani** (IRIF) figures among the nine new honorary doctors appointed at Faculty of Science and Technology of Uppsala University. His research focuses on veriﬁcation, speciﬁcation and semantics for parallel and distributed programs and computer systems.

*12.12.2022*

**Jonas Landman**, former PhD student at IRIF, is the 2022 winner of a **thesis Prize from Chancellerie des Universités de Paris**. His thesis “Quantum Algorithms for Unsupervised Machine Learning and Neural Networks” was awarded in the **All Specialties Science Prize Category**.

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

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

## Agenda

Algorithms and complexity

Monday January 30, 2023, 11AM, Salle 3052

**Samson Wang** (Imperial College London) *Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra*

Verification

Monday January 30, 2023, 11AM, 1007 and Zoom link

**Sylvain Perifel** (IRIF) *Deterministic pushdown automata can compress some normal sequences*

Normality has been introduced by É. Borel more than one hundred years ago. A real number is normal to an integer base if, in its infinite expansion expressed in that base, all blocks of digits of the same length have the same limiting frequency. Normality can also be characterized by non-compressibility by finite state machines. In this talk, we will present a new result showing that pushdown machines, even deterministic, can compress some normal sequences. This solves positively a question left open by V. Becher, P. A. Heiber and O. Carton.

One world numeration seminar

Tuesday January 31, 2023, 2PM, Online

**Slade Sanderson** (Universiteit Utrecht) *Matching for parameterised symmetric golden maps*

Joint with Karma Dajani.

Algorithms and complexity

Wednesday February 1, 2023, 2PM, Salle 3052

**Vincent Cohen-Addad** (Google Research) *Recent Progress on Correlation Clustering: The Power of Sherali-Adams and New Practical insights*

We will first present a new result showing that a constant number of rounds of the Sherali-Adams hierarchy yields a strict improvement over the natural LP: we present the first better-than-two approximation for the problem, improving upon the previous approximation of 2.06 of Chawla, Makarychev, Schramm, Yaroslavtsev based on rounding the natural LP (which is known to have an integrality gap of 2). We will then review several recent ideas which have led to practical constant factor approximations to Correlation Clustering in various setups: distributed and parallel environments, differentially-private algorithms, dynamic algorithms, or sublinear time algorithms.

This is a combination of joint works with Euiwoong Lee, Alantha Newman, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski, Chenglin Fan and Andreas Maggiori.

Enumerative and analytic combinatorics

Thursday February 2, 2023, 11AM, IHP

**Seminaire Flajolet** (Vincent Juge, Jang Soo Kim, Olya Mandelshtam) *IHP*

PhD students seminar

Thursday February 2, 2023, 4PM, 3052 and Zoom link

**Aymeric Walch** *The categorical semantic iceberg finally explained*

After a quick review of the idea behind denotational semantic, we will show that the word “denotational” can in fact be replaced by the word “categorical”. A program will not be interpreted as a mere function, but rather as a morphism in some category. This enlargement of perspective allows us to consider a lot more interesting interpretations for programs: relations, games, probability kernels…

We will then cover the basic categorical ingredients that makes a category a good candidate for interpreting computation. That is, a category must handle tupling and curryfication. If the time allows for it, we will then quickly introduce how those categorical ideas lead to the development of linear logic.

This talk *will not* assume any prior knowledge in category theory nor in denotational semantic.

Analysis and conception of systems

Thursday February 2, 2023, 2PM, salle séminaires au plateau SCAI +(Esclangon, 1er étage, campus Jussieu)

**Marine Minier** (Université de Lorraine) *Comment les outils automatiques peuvent nous aider, nous cryptographes*

Higher categories, polygraphs and homotopy

Friday February 3, 2023, 2PM, Salle 1007

**Pierre-Louis Curien & Guillaume Laplante-Anfossi** (IRIF & Melbourne University) *Une preuve simple et connexe du théorème de cohérence de MacLane*

Dans la deuxième partie, on s'intéressera à l'instanciation du théorème général à la classe des “hypergraph polytopes” (aussi connus sous le nom de nestoèdres), dont les faces (et en particulier les sommets et les arêtes) sont décrits par des objets combinatoires appelés “constructs”. Les arêtes sont naturellement orientées à l'aide d'un ordre appelé ordre de Tamari généralisé, et lorsqu'on instancie encore davantage, à la classe des opéraèdres, on obtient un système de réécriture de termes convergent (sous-jacent au problème de cohérence des opérades catégorifiées de Dosen et Petric), ce qui permet dans ce cas d'obtenir la cohérence par des méthodes de réécriture (complétion de Squier). Les diagrammes obtenus sont légèrement différents de ceux de Dosen et Petric.

Automata

Friday February 3, 2023, 2PM, Salle 3052

**Florent Koechlin** *Two criteria to prove the inherent ambiguity of bounded context-free languages*

Although they made it possible to prove the inherent ambiguity of several languages, as for example the language L = a^n b^m c^p with n=m or m=p, iteration techniques are still very laborious to implement, are very specific to the studied language, and seem even sometimes unadapted. For instance, the relative simplicity of the proof of inherent ambiguity of L completely collapses by replacing the constraint "n=m or m=p" by "n≠m or m≠p". In this talk, I will present two useful criteria based on generating series to prove easily the inherent ambiguity of some bounded context-free languages. These languages, which have a rational generating series, resisted both the classical iteration techniques developed in the 1960’s and the analytic methods introduced by Philippe Flajolet in 1987.

Verification

Monday February 6, 2023, 11AM, 1007 and Zoom link

**Claudio Gomes** (University of Aarhus) *Application of formal methods to verification of self-adaptation loops in digital twins*