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 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 ! 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”. 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. 12.3.2024 Hugo Herbelin, directeur de recherche Inria à l'IRIF, organise la prochaine journée Horizon Maths sur le sujet : Preuve mathématique et sûreté logicielle. Elle aura lieu le mercredi 27 mars 2024 de 9h à 18h à l'institut Henri Poincaré (5 rue Pierre et Marie Curie, Paris 5e), amphithéâtre Hermite. Inscription gratuite mais obligatoire : 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. 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. 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. 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. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Agenda Séminaire des membres non-permanents Jeudi 2 mai 2024, 16 heures, Salle 3052 Ulysse Lechine Introduction to Kolmogorov complexity In 1963 Andrey Kolmogorov came up with the definition of Kolmogorov complexity : the kolmogorov complexity of a string $w\in {0;1}^*$ noted $K(w)$ is the size of the smallest program $p$ which stops after printing $w$. In this sense it can for instance be made formal to say that 0101010101010101 is a less random/complex string than 56748195473159418. This notion of complexity is universal and robust (for instance it doesn't matter in which language the program $p$ is written), it has been studied for its own sake and is also used in number theory, combinatorics, probabilisic theory, computability theory, complexity theory (P=NP) etc… where it has led to new or simplified proofs. We will present an introduction to Kolmogorov theory and some beautiful applications. We will also talk about a new recent result of Léchine and Seiller ( https://hal.science/hal-04539439 ) which features a very neat open combinatorics problem which you may help solve. No background is needed. La syntaxe rencontre la sémantique Jeudi 2 mai 2024, 14 heures, Salle 3071 Mariana Milicich (IRIF, Universite Paris Cite) Hybrid Intersection Types for PCF I will present a type system based on non-idempotent intersection types for PCFh, a variant of PCF. Evaluation in PCFh is hybrid: call-by-name (CBN) and call-by-value (CBV) behaviours cohabit together. Specifically, function application follows CBV semantics, while recursion has a CBN flavour. This hybrid nature is reflected in the type system, which turns out to be sound and complete with respect to PCFh evaluation. This means not only that typability implies normalisation, but also that the converse holds. Moreover, the type system is quantitative, since the size of typing derivations provides upper bounds for the length of normalisation sequences. By refining this type system, we obtain a tight type system, which offers exact information regarding the length of normalisation sequences. Catégories supérieures, polygraphes et homotopie Vendredi 3 mai 2024, 14 heures, Salle 3058 Félix Loubaton (MPIM) Construction de Grothendieck lax La construction de Grothendieck est une construction fondamentale de la théorie des catégories. Dans cet exposé, j'en donnerai une généralisation dans le cadre des $\omega$-catégories faibles. À cette fin, je présenterai quelques concepts importants de la théorie des $\omega$-catégories faibles, tels que les transformations lax, les (co)limites lax, et les fibrations cartésiennes. Enfin, j'expliquerai comment ce résultat peut être utilisé pour donner des calculs explicites d'extensions de Kan lax. Vérification Lundi 6 mai 2024, 11 heures, 3052 and Zoom link Giovanni Bernardi (IRIF) Non encore annoncé. One world numeration seminar Mardi 7 mai 2024, 14 heures, Online Tom Kempton (University of Manchester) The Dynamics of the Fibonacci Partition Function The Fibonacci partition function $R(n)$ counts the number of ways of representing a natural number $n$ as the sum of distinct Fibonacci numbers. For example, $R(6)=2$ since $6=5+1$ and $6=3+2+1$. An explicit formula for $R(n)$ was recently given by Chow and Slattery. In this talk we express $R(n)$ in terms of ergodic sums over an irrational rotation, which allows us to prove lots of statements about the local structure of $R(n)$. IRIF Distinguished Talks Series Mardi 14 mai 2024, 11 heures, TBA Omer Reingold (Stanford) The multitude of group affiliations: Algorithmic Fairness, Loss Minimization and Outcome Indistinguishability We will survey a rather recent and very fruitful line of research in algorithmic fairness, coined multi-group fairness. We will focus on risk prediction, where a machine learning algorithm tries to learn a predictor to answer questions of the form “what is the probability that patient x will experience a particular medical condition?” Training a risk predictor to minimize a loss function fixed in advance is the dominant paradigm in machine learning. However, global loss minimization may create predictions that are mis-calibrated on sub-populations, causing harm to individuals of these populations. Multi-group fairness tries to prevent forms of discrimination to a rich (possibly exponential) collection of arbitrarily intersecting groups. In a sense, it provides a computational perspective on the meaning of individual risks and the classical tension between clinical prediction, which uses individual-level traits, and actuarial prediction, which uses group-level traits. While motivated in fairness, this alternative paradigm for training an indistinguishable predictor is finding a growing number of appealing applications, where the same predictor can later be used to optimize one of a large set of loss functions, under a family of capacity and fairness constraints and instance distributions. Based on a sequence of works joint with (subsets of) Cynthia Dwork, Shafi Goldwasser, Parikshit Gopalan, Úrsula Hébert-Johnson, Lunjia Hu, Adam Kalai, Christoph Kern, Michael P. Kim, Frauke Kreuter, Guy N. Rothblum, Vatsal Sharan, Udi Wieder, Gal Yona and others. Séminaire des membres non-permanents Jeudi 16 mai 2024, 16 heures, Salle 3052 Roman Kniazev Non encore annoncé. Automates Vendredi 17 mai 2024, 14 heures, Salle 3052 Laure Daviaud Non encore annoncé. Combinatoire énumérative et analytique Mardi 21 mai 2024, 11 heures, Salle 3058 Jang Soo Kim (Sungkyunkwan University (SKKU)) Non encore annoncé. Algorithmes et complexité Mardi 21 mai 2024, 15 heures, Salle 4052 (PCQC) Xiaodi Wu (University of Maryland) Non encore annoncé.