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 17.6.2025 Congrats to Niklas Kochdumper (former Postdoc at IRIF), Mohammed Foughali, Peter Habermehl and Eugene Asarin whom received the Best Repeatability Award at HSCC 2025 for their paper “Robust Identification of Hybrid Automata from Noisy Data” 18.6.2025 IRIF is proud to announce that Mickaël Laurent (PhD student), whose thesis co-supervised by Kim Nguyen at the LMF laboratory, has just received the 2025 GPL (Software Engineering and Programming) thesis award 18.6.2025 Mouloud Amara (MPRI student), Mohammed Foughali, Giovanni Bernardi and Adrian Francalanza (University of Malta) will receive a Distinguished Paper Award at ECOOP 2025 for their paper “A theory of (Linear-Time) Timed Monitors”. Realised for the most part during Mouloud Amara's first year of MPRI (TRE + summer internship), this is the first work that solves the monitorability problem for an expressive timed logic (proposed also by the authors). Find more details on Hal 17.6.2025 Congratulations on the five papers co-authored by IRIF members accepted at the CRYPTO 2025 conference (a top-tier conference and one of the two major conferences in cryptography) ! Cryptography is a recent and expanding research area at IRIF, with the arrival of Christina Boura (UPC Professor) and Michele Orrù (CNRS Research Fellow) last year, and these results demonstrate excellent momentum for this research theme at IRIF (including notably a paper by Christina Boura, and a paper by Ioanna Karantaidou, Michele Orrù's postdoc). The list of papers concerned: Find the complete list of papers accepted at CRYPTO 2025 Or the more detailed list with paper abstracts 23.5.2025 We are very proud to announce that nine papers by ten IRIF researchers have been selected for the 2025 ICALP conference! Congratulations to Pierre Fraigniaud, Frédéric Magniez, Simon Apers, Mikaël Rabie, Miklos Santha, Simon Apers, Giannos Stamoulis, Olivier Idir, Valérie Berthé, Junyao Zhao and Thomas Colcombet. You can find here all the accepted papers 2.6.2025 https://www.irif.fr/portraits/erc_hherbelin_pamellies edit all the past news (These news are displayed using a randomized-priority ranking.) Agenda Verification Monday June 23, 2025, 11AM, 3052 and Zoom link Sergio Yovine (Universidad ORT Uruguay) An Approach for Verifying Constrained Large Language-Models Verification of large language models is increasingly attracting attention motivated by their intended use in critical or sensible applications. In this talk we discuss a way to approach this question formally. It is based on two main elements. The first one consists in appropriately defining the composition of a language model with a controller that guides/controls its output. The second one refers to the automata-theoretic characterization of the probability distribution defined by the composition. Here, the focus is put on computing that model subject to suitable equivalence relations by means of algorithms that learn the associated congruences on strings. Like in standard model-checking frameworks, (probabilistic) temporal logic properties can be verified. Experimental results in concrete though still simple scenarios are encouraging but pinpoint interesting research challenges. Distributed algorithms and graphs Tuesday June 24, 2025, 3:30PM, 3052 Hector Buffière (IRIF/ Université Paris Cité) Decomposing graphs into stable and ordered parts The model-theoretic study of graph classes have seen a growing interest recently, linked to the problem of model-checking for first order logic. Two central tools in this study are transductions and decompositions. A transduction can be viewed as a function defined in some logic between classes of graphs, and a decomposition is a way to break a complex graph class into simpler ones by parametric colorings. Both can give interesting perspectives on common width parameters, and are related to some of the core conjectures in this area. We formulate a new conjecture, namely that every dependent hereditary class of graph is a transduction of a dependent hereditary class, consisting of a nowhere dense class of graphs expanded by a tree order. As a first step to attack this problem, we show that every class of bounded linear clique-width admits a transduction pairing with a coupling of a class of bounded pathwidth graphs and a class of partial orders with bounded pathwidth cover graphs. We strengthen this result to classes admitting low linear clique-width decompositions. Algorithms and complexity Wednesday June 25, 2025, 11AM, Salle 3052 Juliette Vlieghe (Technical University of Denmark) Sparsity parametrised dynamic edge colouring We study the edge-colouring problem, and give efficient algorithms where the number of colours is parameterised by the graph's arboricity, $\alpha$. In a dynamic graph, subject to insertions and deletions, we give a deterministic algorithm that updates a proper $\Delta + O(\alpha)$ edge-colouring in $\operatorname{poly}(\log n)$ amortized time. Our algorithm is fully adaptive to the current value of the maximum degree and arboricity. In this fully-dynamic setting, the state-of-the-art edge-colouring algorithms are either a randomised algorithm using $(1 + \varepsilon)\Delta$ colours in $\operatorname{poly}(\log n, \epsilon^{-1})$ time per update, or the naive greedy algorithm which is a deterministic $2\Delta -1$ edge-colouring with $\log(\Delta)$ update time. Compared to the $(1+\varepsilon)\Delta$ algorithm, our algorithm is deterministic and asymptotically faster, and when $\alpha$ is sufficiently small compared to $\Delta$, it even uses fewer colours. In particular, ours is the first $\Delta+O(1)$ edge-colouring algorithm for dynamic forests, and dynamic planar graphs, with polylogarithmic update time. Additionally, in the static setting, we show that we can find a proper edge colouring with $\Delta + 2\alpha$ colours in $O(m\log n)$ time. Moreover, the colouring returned by our algorithm has the following local property: every edge $uv$ is coloured with a colour in $\{1, \max\{deg(u), deg(v)\} + 2\alpha\}$. The time bound matches that of the greedy algorithm that computes a $2\Delta-1$ colouring of the graph's edges, and improves the number of colours when $\alpha$ is sufficiently small compared to $\Delta$. Automata Friday June 27, 2025, 2PM, Salle 3052 Florian Luca (Stellenbosch University) Irrationality and transcendence in the “poor man adèle's ring” We discuss arithmetic questions related to the 'poor man's adèle ring' $\mathcal A$ whose elements are encoded by sequences $(t_p)_p$ indexed by prime numbers, with each $t_p$ viewed as a residue in $\mathbb Z/p\mathbb Z$. Our main theorem is about the $\mathcal A$-transcendence of the element $(F_p(q))_p$, where $F_n(q)$ (Schur's $q$-Fibonacci numbers) are the $(1,1)$-entries of $2\times2$-matrices $$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ q & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ q^2 & 0 \end{pmatrix} \cdots \begin{pmatrix} 1 & 1 \\ q^{n-2} & 0 \end{pmatrix} $$ and $q>1$ is an integer. This result was previously known for $q>1$ square free under the GRH. Distributed algorithms and graphs Tuesday July 8, 2025, 3PM, 3052 Chinh T. Hoang (Wilfrid Laurier University) - Algorithms and complexity Wednesday July 9, 2025, 3PM, Salle 3071 Haotian Jiang (University of Chicago) Quasi-Monte Carlo Integration via Algorithmic Discrepancy Theory A classical approach to numerically integrating a function $f$ is Monte Carlo (MC) methods. Here, one evaluates $f$ at random points and the estimation error scales as $\sigma(f)/n^{1/2}$ with $n$ samples, where $\sigma(f)$ is the standard deviation of $f$. A different approach, widely used in practice, is using quasi-Monte Carlo (QMC) methods, where $f$ is evaluated at carefully chosen deterministic points and the error scales roughly as $1/n$. Both methods have distinctive advantages and shortcomings, and a key question has been to find a method that combines the advantages of both. In this talk, I will introduce the fascinating area of QMC methods and their connections to various areas of mathematics and to geometric discrepancy. I will then show how recent developments in algorithmic discrepancy theory can be used to give a method that combines the benefits of MC and QMC methods, and even improves upon previous QMC approaches in various ways. The talk is based on joint work with Nikhil Bansal (University of Michigan).