image/svg+xml Bienvenue L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université de Paris, qui 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. Six de ses membres ont été lauréats de l'European Research Council (ERC), cinq 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. Tweets by IRIF_Paris Notion du jour Actualités 18.1.2022 Two papers coauthored by IRIF members will be presented at the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) held in Marseille, March 15-18 2022. 17.12.2021 Paul-André Melliès (IRIF), Arthur Vale, Zhong Shao, Jérémie Koenig (Yale) and Léo Stefanesco (MPI) will present a layered concurrent object-based game semantics for the purpose of compositional software specification and certification at annual Symposium on Principles of Programming Languages, POPL2022 : https://hal.inria.fr/hal-03456034. 13.12.2021 Delia Kesner (IRIF) will present her paper A Fine-Grained Computational Interpretation of Girard’s Intuitionistic Proof-Nets at annual Symposium on Principles of Programming Languages, POPL2022. The paper introduces a functional term calculus that captures the essence of the operational semantics of Intuitionistic Linear Logic Proof-Nets with a faithful degree of granularity, both statically and dynamically. 2.12.2021 We are excited to be part of the “High-Performance Computer and Quantum Simulator hybrid” (HPCQS) aiming at creating a world-class supercomputing ecosystem. Learn more about the project here. 29.11.2021 IRIF has the great pleasure to welcome a new professor in computer science at Université de Paris: Matěj Stehlík, an expert in graph theory. Learn more about him and his work here. 1.12.2021 Prochaine conférence dans le cadre des 75 ans d’informatique : L’informatique dans le 7ème art : fiction ou réalité ? Rendez-vous avec Fabrice Kordon le jeudi 9 décembre-18h00 sur le campus Pierre et Marie Curie de Sorbonne Université (tour 25.26, 1er étage – salle 105). 2.12.2021 IRIF is very pleased to host for two months Serge Massar, Professor at the Université libre de Bruxelles (ULB) as part of the FSMP Distinguished Professor Fellowship. Serge Massar is the director of the Laboratoire d'Information Quantique (LIQ), of the Physics Department, Science Faculty, ULB. His research interests are quantum information theory, experimental quantum and non linear optics, machine learning. 13.12.2021 Jacques Sakarovitch (IRIF) was elected new IFIP Fellow. IFIP Fellow is the most most prestigious IFIP's technical distinction which is conferred by the IFIP General Assembly on a current or past member of an IFIP body in recognition of outstanding contributions in the field of information processing, in the role of a Technical Leader, Scientist, Engineer, or Educator. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Agenda Algorithmes et complexité Mardi 25 janvier 2022, 14 heures, 3052 Simona Etinski (INRIA / IRIF) Latest challenges in post-quantum cryptography In 2016, the National Institute of Standards and Technology (NIST) announced a call for standardization (also known as “NIST competition”) of post-quantum cryptographic protocols, i.e., cryptographic protocols considered to be resistant to quantum attacks. NIST was mainly interested in two types of protocols: digital signatures and encryption/key-establishment schemes. The fourth and final round of this competition is about to start, and once it is finished, the most efficient and thoroughly analyzed protocols will be standardized. In this talk, we focus on the proposal for a digital signature. It is based upon a problem from coding theory, known as a syndrome decoding problem, and analyzed using cryptanalytic means. Namely, we analyze the time complexity of the information set decoding algorithms, widely believed to be the best algorithms for solving the syndrome decoding problem. By evaluating their complexity, both in the classical and quantum domain, we reason about the hardness of the problem. Finally, we give an example of the scheme based upon the syndrome decoding problem and analyze its security imposed by the hardness of the problem. We examine the tradeoff between signature's security and its size, which is a major challenge to be addressed in the competition. One world numeration seminar Mardi 25 janvier 2022, 14 heures 30, Online Claudio Bonanno (Università di Pisa) Infinite ergodic theory and a tree of rational pairs The study of the continued fraction expansions of real numbers by ergodic methods is now a classical and well-known part of the theory of dynamical systems. Less is known for the multi-dimensional expansions. I will present an ergodic approach to a two-dimensional continued fraction algorithm introduced by T. Garrity, and show how to get a complete tree of rational pairs by using the Farey sum of fractions. The talk is based on joint work with A. Del Vigna and S. Munday. Combinatoire énumérative et analytique Jeudi 27 janvier 2022, 14 heures, Salle 3052 et sur zoom Elba Garcia-Failde (IMJ-PRG Sorbonne Universite) Une dualité triple : symplectique, simple et libre Dans cet exposé, je présenterai trois transformations qui apparaissent dans des contextes très différents : des cartes combinatoires qui se simplifient, des cumulants qui se libèrent, et des x et y qui s’échangent symplectiquement dans la récurrence topologique. J'expliquerai comment réaliser toutes ces dualités par le biais d’une transformation universelle qui utilise les nombres de Hurwitz monotones doubles. Exprimer la transformation comme l’action d'un opérateur dans l'espace de Fock nous permet d'utiliser les techniques récentes développées par Bychkov, Dunin-Barkowski, Kazarian et Shadrin pour trouver des relations fonctionnelles reliant les séries génératrices des moments d'ordre supérieur et des cumulants libres, ce qui résout un problème ouvert posé par Collins, Mingo, Sniady et Speicher lors du développement de la théorie de second ordre qui généralise la transformée R de Voiculescu. Cela nous conduit à une théorie générale de la liberté qui prend en compte les corrections de genre supérieur qui apparaissent naturellement dans les deux autres contextes. Nous introduisons une notion de cumulants libres surfaciques à partir de la combinatoire du poset de permutations surfaciques (une généralisation des permutations partitionnées) qui capture les développements asymptotiques de tout ordre dans les modèles de matrices aléatoires avec invariance unitaire. Basé sur un travail en commun avec Gaëtan Borot, Severin Charbonnier, Felix Leid et Sergey Shadrin. Preuves, programmes et systèmes Jeudi 27 janvier 2022, 10 heures 30, Room 3052 and virtual room at link (any password works) Titouan Carette (LORIA / Université de Lorraine) Diagrammatic semantics of quantum streams In the same way we have streams of bits and stream transformer, we can define streams of qubits and qubit stream transformers. I will present an extension of quantum circuits with quantum memories to represent stream tranfsormers. We provide a set of rewriting rule and a coinduction principle that can extend any complete set of rules for cirucits to a complete set of rule for stream transformer. Thus, any two observationaly equivalent stream transformers can be proven equivalent using our rewriting rules. I will also expose ongoing works on the denotational semantics of stream transformers and extension to the post selectioned case. Automates Vendredi 28 janvier 2022, 14 heures 30, Salle 3052 Soumyajit Paul A Bridge between Polynomial Optimization and Games with Imperfect Recall Graph Transformation Theory and Applications Vendredi 28 janvier 2022, 15 heures, online William Waites (University of Strathclyde, Scotland, UK) Rule-based Models of Epidemics Rule-based models, a particular kind of graph rewriting system initially intended for use in molecular biology, are conspicuously useful for understanding epidemics. They enable formulation of complex processes that blends the ease of understanding of “compartmental” models with the expressiveness of individual- or agent-based models. We illustrate this with a story, told in graph rewriting rules, of how the adaptive immune response to a pathogen works (simplified version) and how this response influences the population level dynamics of an epidemic. This model can be calibrated against real-world data and we see how some of the individual heterogeneity that is normally treated phenomenologically in the study of epidemics arises naturally from this account of immune response. Zoom meeting registration link YouTube live stream One world numeration seminar Mardi 1 février 2022, 14 heures 30, Online Jonas Jankauskas (Vilniaus universitetas) Non encore annoncé. Combinatoire énumérative et analytique Jeudi 3 février 2022, 14 heures, IHP Amphi Darboux Seminaire Flajolet Jiang Zeng et Marie Albenque http://semflajolet.math.cnrs.fr/index.php/Main/HomePage Automates Vendredi 4 février 2022, 14 heures 30, Salle 3052 (Online) Bartek Klin Orbit-finite-dimensional vector spaces, with applications to weighted register automata I will discuss vector spaces spanned by orbit-finite sets. These spaces are infinite-dimensional, but their sets of dimensions are so highly symmetric that the spaces have many properties enjoyed by finitely-dimensional spaces. Applications of this include a decision procedure for equivalence of weighted register automata, which are the common generalization of weighted automata and register automata for infinite alphabets. The algorithm runs in exponential time, and in polynomial time for a fixed number of registers. As a special case, we can decide, with the same complexity, language equivalence for unambiguous register automata. (Joint work with Mikołaj Bojańczyk and Joshua Moerman.) One world numeration seminar Mardi 8 février 2022, 14 heures 30, Online Magdaléna Tinková (Univerzita Karlova) Non encore annoncé.