Institut de Recherche en Informatique Fondamentale (IRIF)

CNRS

Université Paris Cité

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.

Follow us on Twitter/X, LinkedIn and Mastodon for our latest news:

LinkedIn Twitter/X Mastodon

27.3.2024
We welcome a new research director at IRIF, Tayssir Touili. Her areas of interest are Malware Detection, Software Verification and Formal Methods. You can meet her in room 4028A.

mirna-dzamonja.jpeg

28.3.2024
The Belgian Mathematical Society (BMS) has awarded Mirna Džamonja (CNRS, IRIF, Université de Paris) with the BMS “Godeaux lecture prize”. “The prize is awarded every year, upon proposal from a BMS board member, to a prominent belgian or international mathematician who is invited to give a talk at a conference in Belgium.” Congratulations!

podcastrechercheclairemathieufc.jpg

19.3.2024
After being increased in September 2023, the budget allocated to the french Higher Education and Research is finally reduced by 904 million euros. The podcast “La Science, CQFD” by France Culture wondered how French research is faring and what direction it is taking. Claire Mathieu, research director at CNRS at IRIF, intervenes.

quentin_aristote.jpg

29.3.2024
Congratulations to Quentin Aristote, doctoral student, who won the Helena Rasiowa prize for the best student paper at the 32nd EACSL conference: Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids

marie-jose_iarifina.jpg

27.3.2024
Marie-Josée Iarifina has joined IRIF to replace Natalia Hacquart as Finance and Accounting Manager. Come and meet her and welcome her to office 4002.

15.3.2024
The 2nd french speaking conference «On éteint, on réfléchit, on discute» organized at Université Paris Cité by François Laroussinie focuses on «Les communs numériques» (“Digital Commons”). Serge Abiteboul and Valerie Peugeot are the invited speakers. It will be held on March 19, 2024, from 4pm to 6pm. This is a free of charge event.

12.3.2024
Hugo Herbelin, research director at Inria in IRIF, is organizing the next french speaking Horizon Maths day on the topic: Mathematical Proof and Software Safety. It will take place on Wednesday, March 27, 2024, from 9 a.m. to 6 p.m. at the Henri Poincaré Institute (5 rue Pierre et Marie Curie, Paris 5th), Hermite amphitheater. Free but mandatory registration:

5.2.2024
Join IRIF as Financial Management Manager! As part of an administrative team supervised by the Administrative Manager and consisting of 5 staff (including 3 managers under your responsibility), you will organise tasks relating to the preparation, implementation and monitoring of financial operations. Application deadline: Friday 23 February 2024. | Planned start date: 1 March 2024

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

Automata
Friday March 29, 2024, 2PM, Salle 3052
Leonid Libkin Embedded finite models and finitely representable databases: a forgotten area ready for a comeback

A question was asked 35 years: can we store an infinite set in a database? Turns out the answer is yes, and for this a set has to be finitely representable. In databases we use logic for querying, and thus finitely represent sets by logical formulas over infinite models. The next question was: what can you ask about such databases? To answer this question we had to go back to the finite world, and thus embedded finite models were born, a mix of finite and the infinite. While theoreticians were happy to talk about AC0 and o-minimality, cell decomposition, and local triviality in the same paper, practitioners asked whether something useful can be built based on these ideas. The 1990s answer was no, computers were too slow, solvers were too immature. But the world doesn’t stand still, and we have witnessed signs of rebirth of this area that at the very least gave us theoreticians lots of fun. In the talk I’ll tell this story and share some thoughts on making finitely representable databases great again.

Type theory and homotopy theory
Friday March 29, 2024, 3:30PM, Salle 3052
Moana Jubert Sémantique de la théorie homotopique des types

Enumerative and analytic combinatorics
Tuesday April 2, 2024, 11AM, Salle 3058
Relâche Séminaire Flajolet le 4 avril

Algorithms and complexity
Tuesday April 2, 2024, 11AM, Salle 3071
Michael Klooß (Aalto University) Adaptive Special Soundness: Improved Knowledge Extraction by Adaptive Useful Challenge Sampling

Proving knowledge soundness of an interactive proof from scratch is often a challenging task. This has motivated the development of various special soundness frameworks which, in a nutshell, separate knowledge extractors into two parts: (1) an extractor to produce a set of accepting transcripts conforming to some structure; (2) a witness recovery algorithm to recover a witness from a set of transcripts with said structure. These frameworks take care of (1), so it suffices for a protocol designer to specify (2) which is often simple®.

However, special soundness fails to adequately capture guarantees provided by simple “probabilistic tests”, e.g., short random linear combinations as used in many lattice-based proof systems. In this talk, I will introduce (adaptive) special soundness, which captures many scenarios and discuss the rewinding-based knowledge extraction. Moreover, I will point out current limitations and open problems with regard to (adaptive) special soundness.

This talk is based on join work with Thomas Attema, Russell W. F. Lai, and Pavlo Yatsyna.

Semantics
Wednesday April 3, 2024, 10:45AM, Salle 3052
Thomas Nowak (LMF) Topological Characterization of Task Solvability in General Models of Computation

The famous asynchronous computability theorem (ACT) relates the existence of an asynchronous wait-free shared memory protocol for solving a task with the existence of a simplicial map from a subdivision of the simplicial complex representing the inputs to the simplicial complex representing the allowable outputs. The original theorem relies on a correspondence between protocols and simplicial maps in round-structured models of computation that induce a compact topology. This correspondence, however, is far from obvious for computation models that induce a non-compact topology, and indeed previous attempts to extend the ACT have failed. This paper shows that in every non-compact model, protocols solving tasks correspond to simplicial maps that need to be continuous. It first proves a generalized ACT for sub-IIS models, some of which are non-compact, and applies it to the set agreement task. Then it proves that in general models too, protocols are simplicial maps that need to be continuous, hence showing that the topological approach is universal. Finally, it shows that the approach used in ACT that equates protocols and simplicial complexes actually works for every compact model. Our study combines, for the first time, combinatorial and point-set topological aspects of the executions admitted by the computation model.

Joint work with Hagit Attiya and Armando Castañeda.

Higher categories, polygraphs and homotopy
Friday April 5, 2024, 2PM, Salle 3058
Yonatan Harpaz Lax limits of model categories

In higher category theory, model categories constitute a powerful manner to encode infinity categories. Unfortunately, it is not always possible to encode an infinity category using a model category, and when this is possible the choice of model category is far from being unique or canonical. Favoring such presentations whenever possible, it is hence natural to investigate which operations on the level of infinity categories can be performed on the model categorical level. In this talk I will describe one such result for the operation of lax limits, showing that, under suitable conditions, if a diagram of inifinity categories is modeled by a diagram of (simplicial combinatorial) model categories, then the lax limit can be performed on the level of model categories. We also obtain results concerning homotopy limits and various intermediate limits. This generalizes previous results of Lurie and of Bergner. Related results were also obtained independently by Balzin.

Algorithms and complexity
Friday April 5, 2024, 11AM, Salle 3052
Yanlin Chen (CWI Amsterdam) A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix

Finding a good approximation of the top eigenvector of a given d × d matrix A is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries of A and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity d^{1.5+o(1)} and one with time complexity \tilde{O}(d^{1.75}) that has a slightly better dependence on the precision of the approximation. Both provide a polynomial speed-up over the best-possible classical algorithm, which needs Ω(d^2) queries to entries of A (and hence Ω(d^2) time). We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-q eigenvectors in time qd^{1.5+o(1)}. We also prove a nearly-optimal lower bound of \tilde{Ω}(d^{1.5}) on the quantum query complexity of approximating the top eigenvector. Our quantum algorithms run a version of the classical power method that is robust to certain benign kinds of errors, where we implement each matrix-vector multiplication with small and well-behaved error on a quantum computer, in different ways for the two algorithms.

Our first algorithm used block-encoding techniques to compute the matrix-vector product as a quantum state, from which we obtain a classical description by a new time-efficient unbiased pure-state tomography algorithm that has essentially optimal sample complexity O(d log(d)/ε^2) and that comes with improved statistical properties compared to earlier pure-state tomography algorithms. Our second algorithm estimated the matrix-vector product one entry at a time, using a new “Gaussian phase estimation” procedure. We also develop a time-efficient process- tomography algorithm for reflections around bounded-rank subspaces, providing the basis for our top-eigensubspace estimation application.

This is the joint work with Ronald de Wolf and András Gilyén.

Enumerative and analytic combinatorics
Tuesday April 9, 2024, 11AM, Salle 3058
Viviane Pons (LISN Univ. Paris Saclay) A venir

Algorithms and complexity
Tuesday April 9, 2024, 11AM, Salle 3052
Christoph Egger (IRIF) To be announced.

One world numeration seminar
Tuesday April 9, 2024, 2PM, Online
Simon Kristensen (Aarhus Universitet) On the distribution of sequences of the form $(q_n y)$

The distribution of sequences of the form $(q_n y)$ with $(q_n)$ a sequence of integers and $y$ a real number have attracted quite a bit of attention, for instance due to their relation to inhomogeneous Littlewood type problems. In this talk, we will provide some results on the Lebesgue measure and Hausdorff dimension on the set of points in the unit interval approximated to a certain rate by points from such a sequence. A feature of our approach is that we obtain estimates even in the case when the sequence $(q_n)$ grows rather slowly. This is joint work with Tomas Persson.