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

*4.10.2024*

The 2024 edition of the **Fête de la Science** has begun! The IRIF will host, from **October 4th to 14th**, 13 elementary and middle school classes who will come to explore computer science through **unplugged activities** and **programming**. We also offer a **quantum program** created in collaboration with the Materials and Quantum Phenomena (MPQ) laboratory for high school classes.

*19.9.2024*

This year, IRIF has set a clear goal: **achieving gender parity among 9th-grade interns**. This is a real challenge, as the proportion of women in computer science is still significantly lower. That's why we are counting on our networks to attract more female applicants than in previous years! A week in our research lab will give interns the chance to discover the world of research and gain a clearer understanding of what computer science really is.

*18.9.2024*

Neha Rino (MPRI intern at IRIF in 2023), Eugène Asarin and Mohammed Foughali won the **Best Paper Award at FORMATS**. This work **formulate and solve** by an efficient algorithm the **problem of quantitative monitoring**: compute a real number characterizing to which extent the given trace of a real-time system satisfies its specification.

*25.9.2024*

CNRS Computer Science is organizing the conference “**Optimization: at the Heart of Challenges in Computer Science**” which will take place on **October 3, 2024**, at the CNRS Headquarters. This event, aimed at industry professionals, decision-makers, and journalists, brings together the scientific community to exchange and share knowledge on this cross-disciplinary topic. Claire Mathieu, Simon Apers and David Saulpic will give talks.

*30.9.2024*

Jean-Louis Krivine, Professor Emeritus at IRIF, has published a book entitled ‘Les décompilateurs - L'Univers en tête’. In it you will find, among other things, a reflection on the **origin of mathematics** and the **link between logic and theoretical computing**, as well as some **paradoxes in quantum mechanics**.

*26.8.2024*

Delia Kesner is guest speaker at the Lambda World international conference to be held in Cadiz (Spain) **from 2 to 4 October 2024**.

*11.9.2024*

Roberto Mantaci and Jean-Baptiste Yunès have published a book entitled “**Basics of Programming and Algorithms, Principles and Applications**”. It provides core content for teaching programming and algorithms, covering algorithm performance analysis and essential Python programming knowledge.

*2.9.2024*

Ashwin Nayak (Professor, University of Waterloo) will be **visiting IRIF from September to October 2024**. His research interests include **quantum algorithms, complexity, and communication**. He has collaborated extensively with Dr. Frédéric Magniez and other members of IRIF on these topics. Building on their research collaborations, Dr. Magniez and he led an international **student exchange program** between Canada and a number of EU institutions, and a PICS project between the Institute for Quantum Computing at U. Waterloo and IRIF. Ashwin is looking forward to renewing these ties in the upcoming visit.

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

## Agenda

Algorithms and complexity

Tuesday October 15, 2024, 11AM, Salle 3052

**Christoph Egger** (IRIF) *On Bounded Storage Key Agreement and One-Way Functions*

In this work, we explore how a minimal use of cryptographic assumptions can help circumvent these lower bounds. We obtain several contributions:

- Assuming one-way functions, we construct a one-round key agreement in the bounded-storage model, with arbitrary polynomial space gap between the participants and the adversary, and communication slightly larger than the adversarial storage. Additionally, our protocol can achieve everlasting security using a second streaming round.

- In the other direction, we show that one-way functions are *necessary* for key agreement in the bounded-storage model with large space gaps. We further extend our results to the setting of *fully-streaming* adversaries, and to the setting of key agreement with multiple streaming rounds.

Our results rely on a combination of information-theoretic arguments and technical ingredients such as pseudorandom generators for space-bounded computation, and a tight characterization of the space efficiency of known reductions between standard Minicrypt primitives (from distributional one-way functions to pseudorandom functions), which might be of independent interest.

Joint work with Chris Brzuska, Geoffroy Couteau and Willy Quach

Semantics

Tuesday October 15, 2024, 3PM, Salle 3071

**Jean Krivine** (IRIF) *Semantics of reversible computations*

One world numeration seminar

Tuesday October 15, 2024, 2PM, Online

**Steven Robertson** (University of Manchester) *Low Discrepancy Digital Hybrid Sequences and the t-adic Littlewood Conjecture*

Specifically, it is shown that any counterexample to the so-called $t$-adic Littlewood Conjecture ($t$-LC) can be used to create a low discrepancy digital Kronecker-Van der Corput sequence. Such counterexamples to $t$-LC are known explicitly over a number of finite fields by, on the one hand, Adiceam, Nesharim and Lunnon, and on the other, by Garrett and the Robertson. All necessary concepts will be defined in the talk.

Proofs, programs and systems

Thursday October 17, 2024, 10:30AM, ENS Lyon

**Tba** *CHOCOLA seminar series*

Non-permanent members' seminar

Thursday October 17, 2024, 4PM, Room 3052

**Niklas Kochdumper** (Post-Doc) *Automated Verification of Dynamic Systems*

Higher categories, polygraphs and homotopy

Friday October 18, 2024, 2PM, Salle 1013

**Anibal Medina Mardones** (UWO) *Framed polytopes and higher structures*

Automata

Friday October 18, 2024, 2PM, Salle 3071

**Fabian Reiter** (LIGM) *Locality via Alternation?*

I will start with an attempt to use logic to extend standard complexity theory to the distributed setting. It turns out that several classical concepts generalize well, including the polynomial hierarchy (and hence the complexity classes P and NP), the Cook-Levin theorem (which identifies Boolean satisfiability as a complete problem for NP), and Fagin's theorem (which characterizes NP as the problems expressible in existential second-order logic). But perhaps more surprisingly, separating complexity classes becomes easier in the general case: when extended to multiple computers, the polynomial hierarchy is provably infinite, while it remains notoriously open whether the same holds in the case of a single computer.

In the second part of the talk, I will use the previous results to address a central question in distributed computing: which problems are purely local, which problems are inherently global, and which problems lie between these extremes? The idea will be to measure locality using quantifier alternation, the key concept underlying the polynomial hierarchy.

The talk is based on my paper “A LOCAL View of the Polynomial Hierarchy”. - Proceedings version: https://doi.org/10.1145/3662158.3662774 - Full version: https://arxiv.org/abs/2305.09538

Algorithms and complexity

Tuesday October 22, 2024, 11AM, Salle 3052

**Adam Wesolowski** (Royal Holloway) *Advances in quantum algorithms for the shortest path problem*

Enumerative and analytic combinatorics

Thursday October 24, 2024, 2PM, Salle 3071

**Mark Skandera** *Une généralisation de la formule des défauts de Deodhar pour la multiplication des éléments de base de Kazhdan-Lusztig*

Proofs, programs and systems

Thursday October 24, 2024, 10:30AM, Salle 3052 & online (Zoom link)

**Jean-Jacques Lévy** *To be announced.*