Bienvenue L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, et héberge une équipe-projet Inria. Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques. L'IRIF regroupe près de deux cents personnes. Sept de ses membres ont été lauréats de l'European Research Council (ERC), trois sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences. Notion du jour Réseaux Sociaux Suivez nous sur LinkedIn, Bluesky et Mastodon : Actualités 17.6.2025 Félicitations aux cinq papiers coécrits par des membres de l'IRIF acceptés à la conférence CRYPTO 2025 (conférence de tout premier plan et l'une des deux conférences majeures en cryptographie). La cryptographie est une thématique récente et en expansion à l'IRIF, avec l'arrivée de Christina Boura (professeure UPC) et de Michele Orrù (CR CNRS) l'an dernier, et ces résultats montrent une belle dynamique de la thématique à l'IRIF (avec notamment un papier de Christina Boura, et un papier de Ioanna Karantaidou, post-doctorante de Michele Orrù). La liste des papiers concernés : Shorter, Tighter, FAESTer: Optimizations and Improved (QROM) Analysis for VOLE-in-the-Head Signature Carsten Baum, Ward Beullens, Lennart Braun, Cyprien Delpech de Saint Guilhem, Michael Klooß, Christian Majenz, Shibam Mukherjee, Emmanuela Orsini, Sebastian Ramacher, Christian Rechberger, Lawrence Roy, Peter Scholl Dynamic Bounded-Collusion Streaming Functional Encryption from Minimal Assumptions Kaartik Bhushan, Alexis Korb, Amit Sahai Merkle Mountain Ranges are Optimal: On the Witness Update Frequency of Cryptographic Accumulators Joseph Bonneau, Jessica Chen, Miranda Christ, Ioanna Karantaidou Transistor: a TFHE-friendly Stream Cipher Jules Baudrin, Sonia Belaïd, Nicolas Bon, Christina Boura, Anne Canteaut, Gaëtan Leurent, Pascal Paillier, Léo Perrin, Matthieu Rivain, Yann Rotella, Samuel Tap ω(1/λ)-Rate Boolean Garbling Scheme from Generic Groups Geoffroy Couteau, Carmit Hazay, Aditya Hegde, Naman Kumar Retrouvez la liste complète des papiers acceptés à CRYPTO 2025 Ou encore la liste plus détaillée avec les abstracts des papiers 18.6.2025 Mouloud Amara (étudiant master MPRI), Mohammed Foughali, Giovanni Bernardi et Adrian Francalanza (Université de Malte) recevront un Distinguished Paper Award à ECOOP 2025 pour leur papier “A theory of (Linear-Time) Timed Monitors”. Ce travail, réalisé en grande partie durant la première année de master de Mouloud Amara (TRE + stage d’été), est le premier qui résout le problème de la monitorabilté pour une logique temporisée expressive (elle-même proposée par les auteurs). Consultez Hal pour avoir plus de détails 20.6.2025 Les chercheurs et enseignants-chercheurs du laboratoire témoignent de leur attachement à ce lieu où l'on vit des moments forts de partage avec les médiateurs lors des exposés et ateliers. Ce contact humain en fait un lieu d'échange unique au monde. Nous apprécions tout particulièrement la place que réserve le Palais de la Découverte aux sciences fondamentales, socle de notre culture scientifique commune. Enfin, nous sommes attachés au lieu, le Palais d'Antin, avec son entrée monumentale, qui rappelle à tous le rôle central que la science, et l'émerveillement qu'elle procure, occupe dans notre patrimoine culturel commun. 17.6.2025 Félicitations à Niklas Kochdumper (ex-Postdoc de l'IRIF), Mohammed Foughali, Peter Habermehl et Eugene Asarin qui ont reçu le Best Repeatability Award à HSCC 2025 pour leur papier “Robust Identification of Hybrid Automata from Noisy Data” 18.6.2025 L'IRIF est fier d'annoncer que Mickaël Laurent (doctorant) dont la thèse co-encadré par Kim Nguyen au laboratoire LMF vient d'obtenir le prix de thèse GPL (Génie Logiciel et Programmation) 2025 2.6.2025 Pour Hugo Herbelin et Paul-André Melliès, le chiffre 4 semble être un porte-bonheur : pendant 4 ans, c'est à 4 qu'ils ont construit leur projet pour finalement obtenir leur bourse Synergie du programme de recherche européen (ERC). Avec Philippe de Groote et Carlos Simpson, la langue naturelle mathématique n'aura plus de secret. Rencontre et échanges avec Hugo Herbelin et Paul-André Melliès, directeurs de recherche Inria, porteurs du projet MALINCA. “Avec notre ERC, nous espérons pouvoir comprendre comment, à l'intérieur d'un texte mathématique (que l'on peut trouver dans un article, dans une page de livre de maths), qui est écrit dans ce que l'on appelle une langue naturelle (anglais, français, etc.), le texte contient en lui-même les éléments de sa correction mathématique.” 23.5.2025 Nous annonçons avec fierté que neuf papiers de dix scientifiques de l'IRIF on été selectionnés pour l'ICALP 2025! Félicitations à Pierre Fraigniaud, Frédéric Magniez, Simon Apers, Mikaël Rabie, Miklos Santha, Giannos Stamoulis, Olivier Idir, Valérie Berthé, Junyao Zhao et Thomas Colcombet. Vous pouvez retrouver ici tous les papiers acceptés edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Agenda Vérification Lundi 23 juin 2025, 11 heures, 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. Algorithmique distribuée et graphes Mardi 24 juin 2025, 15 heures 30, 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. Algorithmes et complexité Mercredi 25 juin 2025, 11 heures, 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$. Automates Vendredi 27 juin 2025, 14 heures, 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. Algorithmique distribuée et graphes Mardi 8 juillet 2025, 15 heures, 3052 Chinh T. Hoang (Wilfrid Laurier University) - Algorithmes et complexité Mercredi 9 juillet 2025, 15 heures, 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).