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 10.2.2025 CNRS EDITIONS has published a new book on the history of calculation, titled 𝐿𝑒 𝑐𝑎𝑙𝑐𝑢𝑙 𝑎̀ 𝑑𝑒́𝑐𝑜𝑢𝑣𝑒𝑟𝑡. Several current and former IRIF researchers contributed to the writing of this book by authoring chapters: ◻️ Part 4: ▪️ Chapter 1 - 𝑳'𝒂𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎𝒆 : 𝒗𝒆𝒓𝒔 𝒍𝒂 𝒓𝒆́𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒄𝒐𝒏𝒄𝒓𝒆̀𝒕𝒆 𝒅𝒆 𝒑𝒓𝒐𝒃𝒍𝒆̀𝒎𝒆𝒔 – Claire Mathieu ▪️ Chapter 2 - 𝑳𝒂 𝒄𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒆́ 𝒂𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎𝒊𝒒𝒖𝒆 – Sylvain Perifel ◻️ Part 9: ▪️ Chapter 1 - 𝑳𝒆𝒔 𝒇𝒐𝒏𝒅𝒆𝒎𝒆𝒏𝒕𝒔 𝒅𝒖 𝒄𝒂𝒍𝒄𝒖𝒍 𝒒𝒖𝒂𝒏𝒕𝒊𝒒𝒖𝒆 – Frédéric Magniez 17.2.2025 Science popularization for all ages! Sophie Laplante, professor at IRIF, contributed to issue 425 of Science & Vie Junior, which features an article on quantum science. After an introductory comic, it's time for clear explanations to better understand the quantum computer and demystify its promises. Encryption, keys, data, computations, and bits… These concepts are presented in an accessible way, allowing everyone, young and old, to explore the mysteries of quantum science with ease! Discover it in Science & Vie! 10.2.2025 Congratulations to the Adrian Vladu, IRIF member, whose paper have been accepted to STOC 2025, an ACM conference: 22.1.2025 The third Paris ACTS, will take place at IRIF, on Wednesday 29 January. P-ACTS is a seminar series focused on connections between Automata theory and Concurrency theory, shared between EPITA, IRIF and LIX. The two speakers will be Laetitia Laversa and Glynn Winskel. The talks will also be broadcasted on Zoom. For the abstracts and more information about the seminar, see this page: 30.1.2025 Congratulations to Esaïe Bauer and Alexis Saurin, whose paper has been accepted for the FoSSaCS 2025 conference! 30.1.2025 Three papers of IRIF Members have been accepted to ESOP 2025. Congratulations to Giovanni Bernardi, Thomas Ehrhard, Claudia Faggian and Giulia Manara! 7.1.2025 We are glad to welcome our new Financial and accounting manager, Chafia Dordoigne. You can meet her in room 4002. 6.1.2025 IRIF wishes you a happy new year, filled with groundbreaking research discoveries, scientific achievements, and personal fulfillment! edit all the past news (These news are displayed using a randomized-priority ranking.) Agenda Verification Monday February 17, 2025, 11AM, 3052 and Zoom link Niklas Kochdumper (IRIF) Robust Identification of Hybrid Automata from Noisy Data In recent years, many different methods for identifying hybrid automata from data have been proposed. However, most of these methods consider clean simulator data, and consequently do not perform well for noisy data measured from real systems. We address this shortcoming with a new approach for the identification of hybrid automata that is specifically designed to be robust to noise. In particular, we propose a new high-level strategy consisting of the following three steps: clustering based on the dynamics identified from a local dataset, state space partitioning using decision trees, and conversion of the decision tree to a hybrid automaton. In addition, we introduce several new concepts for the realization of the single steps. For example, we propose an automated regularization of the dynamic models used for clustering via rank adaption, as well as a new variant of the Gini impurity index for decision tree learning, tailored toward hybrid systems where different dynamics can be active within the same state space region. As our experiments on 19 challenging benchmarks with different characteristics demonstrate, in addition to being robust to both process and measurement noise, our approach avoids the need for extensive hyper-parameter tuning and also performs well for clean data without noise. Distributed algorithms and graphs Tuesday February 18, 2025, 3PM, 3052 Bernadette Charron-Bost (Ens Paris) Know your audience (Communication models and function computability in anonymous networks) In this talk, we present exact characterizations of the functions that are computable in anonymous networks with varying assumptions in the degree of awareness or control that agents have over their outneighbors. First, we characterize the computable functions in the “blind broadcast” model, i.e., when agents have no information on their outgoing neighborhoods. Then we enrich this communication model with either output port awareness, bidirectional channels, or outdegree awareness: In each case, we prove that a function can be computed if and only it is frequency-based, namely, its value only depends on the frequencies of the different input values. This characterization holds for both exact and approximate computability. If one or several nodes are distinguished as leaders, or if the cardinality of the network is known, then under any of the above three assumptions it becomes possible to compute any symmetric function. Semantics Tuesday February 18, 2025, 3PM, Salle 3071 Quentin Aristote Monotone weak distributive laws over the lifted powerset monad in categories of algebras Noticing the similarity between the monotone weak distributive laws combining two layers of non-determinism in sets and in compact Hausdorff spaces, we study whether the latter law can be obtained automatically as a weak lifting of the former. This holds partially, but does not generalize to other categories of algebras: we then characterize when exactly monotone weak distributive laws over powerset monads in categories of algebras exist, exhibiting a law combining probabilities and non-determinism in compact Hausdorff spaces and showing on the other hand that such laws do not exist in a lot of other cases. One world numeration seminar Tuesday February 18, 2025, 2PM, Online Neil Macvicar (Queen's University) Intersecting Cantor sets generated by Complex Radix Expansions Consider the classical middle third Cantor set. This is a self-similar set containing all the numbers in the unit interval which have a ternary expansion that avoids the digit 1. We can ask when the intersection of the Cantor set with a translate of itself is also self-similar. Sufficient and necessary conditions were given by Deng, He, and Wen in 2008. This question has also been generalized to classes of subsets of the unit interval. I plan to discuss how existing ideas can be used to address the question for certain self-similar sets with dimension greater than one. These ideas will be illustrated using a class of self-similar sets in the plane that can be realized as radix expansions in base $-n+i$ where $n$ is a positive integer. I will also discuss a property of the fractal dimensions of these kinds of intersections. Non-permanent members' seminar Thursday February 20, 2025, 4PM, Salle 3052 Miriam Marzaioli A Crèche Introduction to Cohen's Forcing In 1963, Paul Cohen discovered the forcing method and definitively answered the first of Hilbert's 23 problems by using this technique to prove the independence of the Continuum Hypothesis from the ZFC axioms. Since then, forcing has become the primary tool in set theory for establishing independence and consistency results. In this talk, we will present the key ingredients and ideas necessary to understand Cohen's model of ZFC + ¬CH. In particular, we will explore Cohen's forcing via the boolean-valued models approach. Automata Friday February 21, 2025, 2PM, Salle 3052 Andrew Ryzhikov (University of Warsaw) How combinatorics stands in the way of matrix reachability (and what we can do about that) Combinatorial automata theory can be seen as studying reachability in transformation semigroups. An interesting way of generalising this setting is by lifting it up to reachability in finite semigroups of rational matrices. Here, besides finite automata theory, other areas come into play, for example weighted automata, algebraic number theory, and multilinear algebra. I will explain several nice questions (such as mortality and minimum rank) that transfer from transformation semigroups to finite matrix semigroups. I will also explain the lack of mathematical structure that is brought by certain PSPACE-complete transformation semigroup problems. Distributed algorithms and graphs Tuesday February 25, 2025, 3PM, 3052 Narges Tavassoli (CRIStAL, Université de Lille) The Parameterized Complexity of Local Search for MOTSP This research aims to connect two important areas: parameterized complexity and multi-objective optimization. Parameterized complexity is a way of studying how efficiently an algorithm can solve a problem by focusing on given parameters, while multi-objective optimization focuses on real-world problems that have several goals to achieve at once. The Multi-Objective Traveling Salesman Problem (MOTSP) is a variation of the Traveling Sales-man Problem (TSP) where a salesman must visit a set of cities and return to the starting point, but instead of optimizing just one objective (like minimizing distance), there are multiple objectives to consider simultaneously. These objectives could be things like minimizing total cost, distance, or travel time, while also considering factors like fuel consumption or safety. We aim to solve MOTSP using a local search method. To enhance the effectiveness of this approach, we have proposed a new neighborhood operator. The Local MOTSP(r-swap) problem takes as input an H-ordered graph G = (V, E), two edge weight functions w1, w2 with maximum weight W, and a positive integer k. The goal is to determine whether there exists an ordered sequence S of at most k r-swaps such that perm(S) results in an improved Hamiltonian cycle. The problem is parameterized by r, k and W. We show that even with multiple objectives, the problem can still be solved in FPT time, specifically in time O(k2·k!·r2(k−1)·n + k5·r ·W4·n2). Semantics Tuesday February 25, 2025, 3PM, Salle 3071 Ariadne Si Suo (Cambridge) Type Checking is Proof Reductions in Classical Linear Logic I will try to convince you type checkers can be seen as logic programs with ‘directions’, and doing type checking correspond to proof reductions in classical linear logic. This gives us implementations of type checking algorithms for free, by writing bidirectional typing rules as directional logic programs. If time permits, I will tell you some categorical details, or possible extensions to accommodate more expressive type systems. Based on joint work with Vikraman Choudhury and Neel Krishnaswami. Special events Wednesday February 26, 2025, 9AM, Amphi Turing, Sophie Germain Sam Van Gool (IRIF & IMJ) Logique à Paris In collaboration with the logic group of the math department (IMJ-PRG), PPS pole is organizing a meeting: Logique à Paris 26 - 28 February 2025 Amphi Turing, Sophie Germain https://www.sylvyanscombe.com/logiqueaparis2025.html Talks are given by six invited speakers on various current topics in logic, which in several cases include interactions with the foundations of computer science: Albert Atserias, Ingo Blechschmidt, Laura Fontanella, Jonathan Kirby, Chris Lambie-Hanson, Mariana Vicaria. Each speaker will give two hours of lectures; typically, the first lecture gives a broad introduction to their domain, followed by a more in-depth talk on a recent topic. If you would like to attend one or more of the talks, we kindly request that you register via the link above. Automata Friday February 28, 2025, 2PM, Salle 3052 Herman Goulet-Ouellet To be announced.