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 4.10.2024 La Fête de la Science édition 2024 est lancée ! L'IRIF et l'Université Paris Cité accueilleront du 4 au 14 octobre, 13 classes de primaire et collège, qui viendront découvrir l'informatique à travers des activités débranchées et de la programmation. Nous proposons également un programme quantique créé avec le laboratoire Matériaux et Phénomènes Quantiques (MPQ) à des classes de lycée. 25.9.2024 CNRS Sciences Informatiques organise la conférence « L'optimisation : au cœur des défis de l'informatique » qui aura lieu le 3 octobre 2024, au siège du CNRS. Cet événement, destiné aux professionnels de l'industrie, aux décideurs et aux journalistes, rassemble la communauté scientifique pour échanger et partager les connaissances sur ce sujet transdisciplinaire. Claire Mathieu, Simon Apers et David Saulpic y interviendront. 30.9.2024 Jean-Louis Krivine, professeur émérite à l'IRIF, a publié un livre, “Les décompilateurs - L'Univers en tête”. Vous y trouverez, entre autres, une réflexion sur l'origine des mathématiques et le lien entre logique et informatique théorique ainsi que quelques paradoxes en mécanique quantique. 18.9.2024 Neha Rino (stagiaire MPRI à l'IRIF en 2023), Eugène Asarin et Mohammed Foughali ont remporté le Best Paper Award à FORMATS. Ce travail formule et résout par un algorithme efficace le problème du suivi quantitatif : calculer un nombre réel caractérisant dans quelle mesure la trace donnée d'un système temps réel satisfait sa spécification. 19.9.2024 Cette année, l'IRIF s'est fixé un objectif clair : atteindre la parité parmi les stagiaires de 3e. Un véritable défi, car dans les sciences informatiques, la proportion de femmes est encore nettement plus faible. C'est pourquoi nous comptons sur nos réseaux pour attirer davantage de candidatures féminines que les années précédentes ! Une semaine dans notre laboratoire de recherche permettra aux stagiaires de découvrir l'univers de la recherche et de mieux comprendre ce qu'est l'informatique. 2.9.2024 Ashwin Nayak (professeur à l'Université de Waterloo) sera en visite à l'IRIF de septembre à octobre 2024. Ses recherches portent sur les algorithmes quantiques, la complexité et la communication. Il a beaucoup collaboré avec le Dr Frédéric Magniez et d'autres membres de l'IRIF sur ces sujets. En s'appuyant sur leurs collaborations de recherche, le Dr. Magniez et lui-même ont dirigé un programme international d'échange d'étudiants entre le Canada et un certain nombre d'institutions de l'UE, ainsi qu'un projet PICS entre l'Institute for Quantum Computing de l'Université de Waterloo et l'IRIF. Ashwin se réjouit de renouer ces liens lors de sa prochaine visite. 11.9.2024 Roberto Mantaci et Jean-Baptiste Yunès ont publié un livre intitulé « Basics of Programming and Algorithms, Principles and Applications ». Il fournit un contenu de base pour l'enseignement de la programmation et des algorithmes, couvrant l'analyse des performances des algorithmes et les connaissances essentielles en programmation Python. 26.8.2024 Delia Kesner est oratrice invitée à la conférence internationale Lambda World qui aura lieu à Cadiz (Espagne) du 2 au 4 octobre 2024. 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 15 octobre 2024, 11 heures, Salle 3052 Christoph Egger (IRIF) On Bounded Storage Key Agreement and One-Way Functions We study key agreement in the bounded-storage model, where the participants and the adversary can use an a priori fixed bounded amount of space, and receive a large stream of data. While key agreement is known to exist unconditionally in this model (Cachin and Maurer, Crypto'97), there are strong lower bounds on the space complexity of the participants, round complexity, and communication complexity that unconditional protocols can achieve. In this work, we explore how a minimal use of cryptographic assumptions can help circumvent these lower bounds. We obtain several contributions: - Assuming one-way functions, we construct a one-round key agreement in the bounded-storage model, with arbitrary polynomial space gap between the participants and the adversary, and communication slightly larger than the adversarial storage. Additionally, our protocol can achieve everlasting security using a second streaming round. - In the other direction, we show that one-way functions are *necessary* for key agreement in the bounded-storage model with large space gaps. We further extend our results to the setting of *fully-streaming* adversaries, and to the setting of key agreement with multiple streaming rounds. Our results rely on a combination of information-theoretic arguments and technical ingredients such as pseudorandom generators for space-bounded computation, and a tight characterization of the space efficiency of known reductions between standard Minicrypt primitives (from distributional one-way functions to pseudorandom functions), which might be of independent interest. Joint work with Chris Brzuska, Geoffroy Couteau and Willy Quach Sémantique Mardi 15 octobre 2024, 15 heures, Salle 3071 Jean Krivine (IRIF) Semantics of reversible computations Like time in physics, computations can be reversible: the inverse of a deterministic computation is itself a valid computation, provided the program's state retains sufficient information to allow rollback. However, reversing a computation in distributed systems presents a challenge due to non-determinism. The inversion process must respect causality to maintain consistency. Syntactically, reversing a concurrent program requires tracking computation events in a way that preserves information during reductions, despite the absence of a global scheduler. From a denotational perspective, traditional models interpret concurrent programs as partial orders of configurations, where configurations consist of sets of computation events. Executing a computation involves removing the corresponding events from all configurations using set difference, while discarding incompatible configurations. In this talk, we introduce a generalization of these traditional models to accommodate reversibility, employing symmetric difference. This approach interprets reversible computation as a partial group action on sets of configurations. One world numeration seminar Mardi 15 octobre 2024, 14 heures, Online Steven Robertson (University of Manchester) Low Discrepancy Digital Hybrid Sequences and the t-adic Littlewood Conjecture The discrepancy of a sequence measures how quickly it approaches a uniform distribution. Given a natural number $d$, any collection of one-dimensional so-called low discrepancy sequences $\{S_i : 1 \le i \le d\}$ can be concatenated to create a $d$-dimensional hybrid sequence $(S_1, . . . , S_d)$. Since their introduction by Spanier in 1995, many connections between the discrepancy of a hybrid sequence and the discrepancy of its component sequences have been discovered. However, a proof that a hybrid sequence is capable of being low discrepancy has remained elusive. In this talk, an explicit connection between Diophantine approximation over function fields and two dimensional low discrepancy hybrid sequences is provided. Specifically, it is shown that any counterexample to the so-called $t$-adic Littlewood Conjecture ($t$-LC) can be used to create a low discrepancy digital Kronecker-Van der Corput sequence. Such counterexamples to $t$-LC are known explicitly over a number of finite fields by, on the one hand, Adiceam, Nesharim and Lunnon, and on the other, by Garrett and the Robertson. All necessary concepts will be defined in the talk. Preuves, programmes et systèmes Jeudi 17 octobre 2024, 10 heures 30, ENS Lyon Tba CHOCOLA seminar series Séminaire des membres non-permanents Jeudi 17 octobre 2024, 16 heures, Room 3052 Niklas Kochdumper (Post-Doc) Automated Verification of Dynamic Systems Reachability analysis is a powerful technique that can be used to verify that dynamic systems, such as autonomous cars, robots, or power grids, are robustly safe despite disturbances, measurement errors, and uncertain behavior of other agents in the environment. However, one substantial bottleneck of all state-of-the-art reachability algorithms is the necessity to adequately tune specific algorithm parameters, such as the time step size, which requires expert knowledge. This talk presents a new type of reachability algorithm, which already tunes all parameters internally until safety of the system with respect to unsafe sets or temporal logic specifications can either be proven or falsified. Our automated algorithm enables also non-experts to apply reachability analysis with ease, and we hope that this will facilitate a more widespread use of formal methods for dynamic systems in both research and industry in the future. Catégories supérieures, polygraphes et homotopie Vendredi 18 octobre 2024, 14 heures, Salle 1013 Anibal Medina Mardones (UWO) Framed polytopes and higher structures A framed polytope is the convex closure of a finite set of points in Euclidean space together with an ordered linear basis. An n-category is a category that is enriched in the category of (n-1)-categories. Although these concepts may initially appear to be distant peaks in the mathematical landscape, there exists a trail connecting them, blazed in the 90's by Kapranov and Voevodsky. We will traverse this path, widening and improving it as we address some of their conjectures along the way. If time permits, using a special embedding of the combinatorial simplex, we will connect this trail to the one ascending Mount Steenrod. This connection will enable us to express the combinatorics of cup-i products in convex geometric terms, dual to those introduced earlier in the talk to define the nerve of higher categories. Automates Vendredi 18 octobre 2024, 14 heures, Salle 3071 Fabian Reiter (LIGM) Locality via Alternation? In this talk, I will show how logic and automata theory can help research in distributed computing. I will start with an attempt to use logic to extend standard complexity theory to the distributed setting. It turns out that several classical concepts generalize well, including the polynomial hierarchy (and hence the complexity classes P and NP), the Cook-Levin theorem (which identifies Boolean satisfiability as a complete problem for NP), and Fagin's theorem (which characterizes NP as the problems expressible in existential second-order logic). But perhaps more surprisingly, separating complexity classes becomes easier in the general case: when extended to multiple computers, the polynomial hierarchy is provably infinite, while it remains notoriously open whether the same holds in the case of a single computer. In the second part of the talk, I will use the previous results to address a central question in distributed computing: which problems are purely local, which problems are inherently global, and which problems lie between these extremes? The idea will be to measure locality using quantifier alternation, the key concept underlying the polynomial hierarchy. The talk is based on my paper “A LOCAL View of the Polynomial Hierarchy”. - Proceedings version: https://doi.org/10.1145/3662158.3662774 - Full version: https://arxiv.org/abs/2305.09538 Algorithmes et complexité Mardi 22 octobre 2024, 11 heures, Salle 3052 Adam Wesolowski (Royal Holloway) Advances in quantum algorithms for the shortest path problem Combinatoire énumérative et analytique Jeudi 24 octobre 2024, 14 heures, Salle 3071 Mark Skandera Une généralisation de la formule des défauts de Deodhar pour la multiplication des éléments de base de Kazhdan-Lusztig Soit H l'algèbre de Hecke d'un groupe de Coxeter (W,S). En étudiant la base Kazhdan-Lusztig de H, Deodhar a considéré les produits C_{w^{(1)} *…* C_{w^{(k)}, où (w^{(1)},… ,w^{(k)}) est une séquence de générateurs dans S. Il a défini et a compté certains “défauts” de telles séquences pour exprimer les produits correspondants dans la base naturelle de H. Nous étendons sa définition à des séquences d'éléments plus généraux de W et exprimons ainsi des produits plus généraux dans la base naturelle de H, dans la cas où W est de type A ou BC. Ce travail a été réalisé en collaboration avec Gavin Hobbs, Tommy Parisi, et Jiayuan Wang. Preuves, programmes et systèmes Jeudi 24 octobre 2024, 10 heures 30, Salle 3052 & online (Zoom link) Jean-Jacques Lévy Non encore annoncé.