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 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.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 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 ! 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 ! 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. 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. 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. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Agenda Combinatoire énumérative et analytique Mardi 16 avril 2024, 11 heures, Salle 3058 Relâche (Vacances De Printemps) Relâche Algorithmes et complexité Mardi 16 avril 2024, 10 heures, Salle 3052 Zvi Lotker (Bar-Ilan University) Narratives: Shaping the Evolution of Social Networks and the Concept of Time (Part 2 of a mini-course of two sessions, 2 hours each) The mini-course explores the way time flows in dynamic social networks. We will use subjective clocks to open a window to the human soul. The course will cover the second part of my book Analyzing Narratives in Social Networks (https://link.springer.com/book/10.1007/978-3-030-68299-6). In the first lecture, we will cover chapters 11, 12, and 13. In the second lecture, we will cover chapters 14, 15, and 16. Chapter 11 studies the perception of time in narrative. We model the narrative of a reader's experience of time as an evolving social network. This chapter takes the function analysis approach, which uses functions as the principal mathematical object. Therefore, the evolving social network is a function of time. Chapter 12 introduces the notion of subjective and objective clocks. We model subjective time in narrative, and introduce a the subjective clock to allow machines to measure subjective time. We define clocks as an increasing monotonic function. This definition deviates from the traditional definition of clocks as oscillators. The advantage of the monotonic definition is that it is inclusive of both psychological/subjective clocks and objective clocks. Chapter 13 explains how to compare clocks. Following the stochastic process definition of Martingales, the basic idea is to remove all Euclidean symmetries (such as translation and rotation) from the two clocks. This is equivalent to removing the linear part of those clocks. We introduce the $M$ diagram, which allows for representation of the two clocks as a function of each other after cancelling the Euclidean symmetry. We compare clocks by finding the point at which clocks begin to deviate from one another. Chapter 14 uses the relationships between clocks to identify critical events in the evolution of a social network. We use the drift between the weighted clock and the event clock to identify critical events in weighted social networks. Chapter 14 defines the law of two clocks, which we can implement in narrative processing. Chapter 15 provides techniques to transform evolving social networks into a real function. This helps us simplify the analysis of social networks. We use these techniques in narrative processing. Chapter 16 defines higher orders of social networks and gives some explanation of evolving social network surfaces. We related social network surfaces to sub-stories within a larger overarching narrative. Catégories supérieures, polygraphes et homotopie Vendredi 19 avril 2024, 14 heures, Salle 3058 Jovana Obradovic A Calculus for S^3-diagrams of Manifolds with Boundary n this talk, we shall introduce a calculus for a presentation of compact, orientable, connected 3-manifolds with boundary in terms of diagrams embedded in S^3 in a form akin to the standard surgery presentation of closed, orientable, connected 3-manifolds. The motivation to introduce such a presentation of manifolds is to give a completely combinatorial description of the category 3Cob, whose arrows are 3-dimensional cobordisms, which is an ongoing project. We hope this could support further investigations of faithfulness of 3-dimensional Topological Quantum Field Theories. This is a joint work with Bojana Femić, Vladimir Grujić and Zoran Petrić. Automates Vendredi 19 avril 2024, 14 heures, Salle 3052 Florent Capelli Direct Access For Conjunctive Queries with Negation Direct Access is the operation of returning, given an index j, the j-th answer of a conjunctive query Q on a given database for some given order on the answers set of Q. While this problem is #P-hard in general (wrt combined complexity), many conjunctive queries are structured enough so that for some lexicographical ordering of their answers, one can have a direct access to the answer of Q that takes polylogarithmic time in the size of the database after polynomial time precomputation. Previous work have precisely characterized the tractable classes and given fine grained lower bounds on the time needed for precomputation depending on the structure of the query. We give a generalization of these tractability results to the case of signed conjunctive queries, that is, conjunctive queries that may contain negative atoms. Our technique is based on solving the ranked access for a class of circuits that can represent relational data. Our result then follows from the fact that the tractable (signed) conjunctive queries can be transformed into polynomial size circuit. We recover the known tractable classes from the literature in the case of positive conjunctive queries using this technique and also discover new island of tractability for signed conjunctive queries. In particular, our result generalizes to the Ranked Access Problem the known tractabilities of counting the number of answers to beta-acyclic negative queries and of deciding whether a negative query with bounded nested-width has an answer. This is join work with Oliver Irwin and appeared at ICDT 2024: - ArXiv version: https://arxiv.org/abs/2310.15800 - Published version: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.13 Vérification Lundi 22 avril 2024, 11 heures, 3052 and Zoom link Sidi Mohamed Beillahi (University of Toronto) Non encore annoncé. Algorithmes et complexité Mardi 23 avril 2024, 11 heures, Salle 3052 Team Event AlgoComp lightning talks ⚡️ One world numeration seminar Mardi 23 avril 2024, 14 heures, Online Shunsuke Usuki (Kyoto University) On a lower bound of the number of integers in Littlewood's conjecture Littlewood's conjecture is a famous and long-standing open problem which states that, for every $(\alpha,\beta) \in \mathbb{R}^2$, $n\|n\alpha\|\|n\beta\|$ can be arbitrarily small for some integer $n$. This problem is closely related to the action of diagonal matrices on $\mathrm{SL}(3,\mathbb{R})/\mathrm{SL}(3,\mathbb{Z})$, and a groundbreaking result was shown by Einsiedler, Katok and Lindenstrauss from the measure rigidity for this action, saying that Littlewood's conjecture is true except on a set of Hausdorff dimension zero. In this talk, I will explain about a new quantitative result on Littlewood's conjecture which gives, for every $(\alpha,\beta) \in \mathbb{R}^2$ except on sets of small Hausdorff dimension, an estimate of the number of integers $n$ which make $n\|n\alpha\|\|n\beta\|$ small. The keys for the proof are the measure rigidity and further studies on behavior of empirical measures for the diagonal action. Séminaire des membres non-permanents Jeudi 25 avril 2024, 16 heures, Salle 3052 Etienne Objois Non encore annoncé. Vérification Lundi 29 avril 2024, 11 heures, 3052 and Zoom link Niklas Kochdumper (IRIF) Non encore annoncé. Combinatoire énumérative et analytique Mardi 30 avril 2024, 11 heures, Salle 3058 Viviane Pons (LISN Univ. Paris Saclay) A venir