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 Mastodon, Twitter/X et LinkedIn : Actualités 28.3.2024 La Société mathématique de Belgique (SMB) a décerné à Mirna Džamonja (CNRS, IRIF, Université de Paris) le “Prix Godeaux” de la SMB. “Ce prix est décerné chaque année, sur proposition d'un membre du conseil d'administration de la BMS, à un-e mathématicien-ne belge ou international-e de renom qui est invité-e à donner une conférence en Belgique”. Toutes nos félicitations ! 29.3.2024 Bravo à Quentin Aristote, doctorant, qui a reçu le prix Helena Rasiowa pour le meilleur papier étudiant, lors de la 32ème conférence EACSL : Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids. 10.4.2024 Trois projets de médiation scientifique de chercheurs à l'IRIF ont été sélectionnés pour l'édition 2024 de Pint of Science France-Paris. Le principe : découvrir une thématique ou un sujet scientifique, dans un bar. Nos chercheurs parleront protection des données, graphes et informatique quantique. 27.3.2024 Marie-Josée Iarifina a rejoint l'IRIF pour remplacer Natalia Hacquart en tant que gestionnaire financière et comptable. Venez la rencontrer et lui souhaiter la bienvenue dans le bureau 4002. 10.4.2024 L'IRIF a le plaisir d'annoncer son deuxième Distinguished Talk de l'année ! Notre conférencier invité est Omer Reingold, professeur d'informatique à l'université de Stanford et directeur de la Simons Collaboration sur la théorie de l'Équité algorithmique (Simons Foundation). Il parlera de l'équité algorithmique. Toute personne intéressée est invitée à se joindre à nous pour cette conférence ! 27.3.2024 Nous accueillons une nouvelle directrice de recherche à l'IRIF, Tayssir Touili. Ses domaines d'intérêt sont la détection de logiciels malveillants, la vérification de logiciels et les méthodes formelles. Vous pouvez la rencontrer dans le bureau 4028A. 19.3.2024 Après avoir été augmenté en septembre 2023, le budget alloué à l’Enseignement supérieur et à la Recherche est finalement réduit de 904 millions d’euros. Le podcast “La Science, CQFD” de France Culture s'est demandé comment se porte la recherche française et quelle direction elle prend. Claire Mathieu, directrice de recherche au CNRS à l'IRIF, intervient. 12.4.2024 La rediffusion de la conférence (en anglais) de Véronique Cortier, qui s'est tenue en février, est désormais disponible sur la chaîne YouTube de l'IRIF. Son sujet était : “Le vote électronique : conception et vérification formelle”. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Agenda Catégories supérieures, polygraphes et homotopie Vendredi 17 mai 2024, 14 heures, Salle 3058 Lyne Moser New methods to construct model categories Model categories provide a good environment to do homotopy theory. A model category consists of a bicomplete category together with three classes of morphisms (weak equivalences, cofibrations, and fibrations) satisfying a list of axioms. While weak equivalences are the main players in a model category and encode how two objects should be thought of as being ``the same, the additional data of cofibrations and fibrations typically facilitates computations of homotopy limits and colimits, and of derived functors. However, because of their robust structure, model categories are usually hard to construct. In joint work with Guetta, Sarazola, and Verdugo, we develop new techniques for constructing model structures from given classes of cofibrations, fibrant objects, and weak equivalences between them. The requirement that one only needs to provide a class of weak equivalences between fibrant objects both simplifies the conditions to check and seems more natural in practice: often, the fibrant objects are the ``well-behaved objects in a model category and so the weak equivalences should only be expected to exhibit a good behavior between these objects. As a straightforward consequence of our result, we obtain a more general version of the usual right-induction theorem along an adjunction, where fibrations and weak equivalences are now only right-induced between fibrant objects; we refer to such an induced model structure as fibrantly-induced. As applications of these new methods, we construct several model structures on the category of double categories. Automates Vendredi 17 mai 2024, 14 heures, Salle 3052 Laure Daviaud Weighted automata: a la carte! I will first give a quick overview of decidability problems for weighted automata. Then, up to you! I can talk about any of the following topics, we'll vote! - decidability of the Big-O problem for max-plus automata - the many undecidability results via the halting problems of two-counter machines - learnability of weighted automata Combinatoire énumérative et analytique Mardi 21 mai 2024, 11 heures, Salle 3058 Jang Soo Kim (Sungkyunkwan University (SKKU)) Lecture hall graphs and the Askey scheme We establish, for every family of orthogonal polynomials in the Askey scheme and the q-Askey scheme, a combinatorial model for mixed moments and coefficients in terms of paths on the lecture hall lattice. This generalizes to all families of orthogonal polynomials in the Askey scheme previous results of Corteel and Kim for the little q-Jacobi polynomials. This is joint work with Sylvie Corteel, Bhargavi Jonnadula, and Jon Keating. Algorithmes et complexité Mardi 21 mai 2024, 15 heures, Salle 4052 (PCQC) Xiaodi Wu (University of Maryland) Hamiltonian-oriented Quantum Algorithm Design and Programming This is an exciting time for quantum computing where early-stage quantum computers become available at your fingertips through clouds. The conventional design of quantum algorithms is centered around the abstraction of quantum circuits and relies on a digital mindset for application design and implementation. While serving as an elegant mathematical interface, circuit-based digital abstraction usually fails to capture the native programmability of quantum devices, and incurs large overheads, which significantly restricts its near-term feasibility where the quantum computing resource is the major limitation. We propose to use quantum Hamiltonian evolution as the central object in end-to-end quantum application design, i.e. the so-called Hamiltonian-oriented paradigm, based on the observation that Hamiltonian evolution is a native abstraction for both low-level hardware control and high-level quantum applications. We illustrate that the Hamiltonian-oriented design not only allows more efficient implementation of existing quantum algorithms but also inspires novel quantum algorithms, especially in optimization and scientific computing, which are hard to perceive in the circuit model. We also develop a programming infrastructure called SIMUQ (SIMUlation language for Quantum) for easy implementation of Hamiltonian-based quantum applications for domain experts on heterogeneous quantum devices. Algorithmes et complexité Mardi 21 mai 2024, 14 heures, Salle 3052 Lawrence Roy (Aarhus University) VOLE-in-the-Head and Post-Quantum Signatures VOLE-in-the-head (closely related to the MPC-in-the-head paradigm of Ishai et al.) is recent technique for computationally efficient but non-succinct NIZK in the random oracle model. It was applied to post quantum signatures in the signature scheme FAEST, a submission to the NIST call for additional digital signature schemes, which works by proving knowledge of an AES key. I will present the VOLE-in-the-head technique, it's application to FAEST, and the recent “One Tree” optimizations. One world numeration seminar Mardi 21 mai 2024, 14 heures, Online Gaétan Guillot (Université Paris-Saclay) Approximation of linear subspaces by rational linear subspaces We elaborate on a problem raised by Schmidt in 1967: rational approximation of linear subspaces of $\mathbb{R}^n$. In order to study the quality approximation of irrational numbers by rational ones, one can introduce the exponent of irrationality of a number. We can then generalize this notion in the framework of vector subspaces for the approximation of a subspace by so-called rational subspaces. After briefly introducing the tools for constructing this generalization, I will present the different possible studies of this object. Finally I will explain how we can construct spaces with prescribed exponents. Sémantique Mercredi 22 mai 2024, 10 heures 30, Salle 3052 Jean-Simon Lemay Free Differential Storage Modalities Storage modalities provide the categorical interpretation of the exponential modality from Linear Logic, while differential storage modalities do the same in Differential Linear Logic. Briefly, a storage modality is a special kind of comonad, while a differential storage modality is a storage modality equipped with a deriving transformation (equivalent a codereclition). In this talk, I’ll explain how using Kelly's notion of algebraically-free commutative monoids, we can construct free differential storage modalities over storage modalities. When taking the initial storage modality, we get the initial differential storage modality which is related to the Faà di Bruno construction and also recaptures the exponential modality in Clift and Murfet's Differential Linear Logic model. This is joint work with Richard Garner. Preuves, programmes et systèmes Jeudi 23 mai 2024, 10 heures 30, ENS Lyon Tba Séminaire CHOCOLA Séminaire des membres non-permanents Jeudi 23 mai 2024, 16 heures, Salle 3052 Dung Bui Non encore annoncé. Catégories supérieures, polygraphes et homotopie Vendredi 24 mai 2024, 10 heures 30, Salle 3052 Wojciech Dulinski (Varsovie) Eilenberg-Zilber opetopic sets and the $(\infty,0)$-model structure In my talk, I will discuss the category $pOpe_\iota$ of positive opetopes with \iota-contractions, introduced by Zawadowski. I will then define the category $\widehat{pOpe_\iota}_{EZ}$ of Eilenberg-Zilber opetopic sets, which are presheaves on $pOpe_\iota$ analogous to simplicial sets. I will outline a modification of Cisinski theory applicable to $\widehat{pOpe_\iota}_{EZ}$, demonstrating the existence of a model structure. Additionally, I will sketch the proof of its Quillen equivalence to the Kan-Quillen model structure. If time allows, I will touch upon another model structure and its potential comparison with the Joyal model structure on simplicial sets.