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 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. 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! 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. 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 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 edit all the past news (These news are displayed using a randomized-priority ranking.) Agenda 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.