Welcome IRIF is a research laboratory of CNRS and Université Paris Cité, also hosting one Inria project-team. The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences. IRIF hosts about 200 people. Seven of its members have been distinguished by the European Research Council (ERC), six are members of the Institut Universitaire de France IUF), two are members of the Academia Europæa, and one is member of Académie des sciences. Notion of the day Social Networks Follow us on Twitter/X, LinkedIn and Mastodon for our latest news: News 4.10.2024 The 2024 edition of the Fête de la Science has begun! The IRIF will host, from October 4th to 14th, 13 elementary and middle school classes who will come to explore computer science through unplugged activities and programming. We also offer a quantum program created in collaboration with the Materials and Quantum Phenomena (MPQ) laboratory for high school classes. 19.9.2024 This year, IRIF has set a clear goal: achieving gender parity among 9th-grade interns. This is a real challenge, as the proportion of women in computer science is still significantly lower. That's why we are counting on our networks to attract more female applicants than in previous years! A week in our research lab will give interns the chance to discover the world of research and gain a clearer understanding of what computer science really is. 18.9.2024 Neha Rino (MPRI intern at IRIF in 2023), Eugène Asarin and Mohammed Foughali won the Best Paper Award at FORMATS. This work formulate and solve by an efficient algorithm the problem of quantitative monitoring: compute a real number characterizing to which extent the given trace of a real-time system satisfies its specification. 25.9.2024 CNRS Computer Science is organizing the conference “Optimization: at the Heart of Challenges in Computer Science” which will take place on October 3, 2024, at the CNRS Headquarters. This event, aimed at industry professionals, decision-makers, and journalists, brings together the scientific community to exchange and share knowledge on this cross-disciplinary topic. Claire Mathieu, Simon Apers and David Saulpic will give talks. 30.9.2024 Jean-Louis Krivine, Professor Emeritus at IRIF, has published a book entitled ‘Les décompilateurs - L'Univers en tête’. In it you will find, among other things, a reflection on the origin of mathematics and the link between logic and theoretical computing, as well as some paradoxes in quantum mechanics. 26.8.2024 Delia Kesner is guest speaker at the Lambda World international conference to be held in Cadiz (Spain) from 2 to 4 October 2024. 11.9.2024 Roberto Mantaci and Jean-Baptiste Yunès have published a book entitled “Basics of Programming and Algorithms, Principles and Applications”. It provides core content for teaching programming and algorithms, covering algorithm performance analysis and essential Python programming knowledge. 2.9.2024 Ashwin Nayak (Professor, University of Waterloo) will be visiting IRIF from September to October 2024. His research interests include quantum algorithms, complexity, and communication. He has collaborated extensively with Dr. Frédéric Magniez and other members of IRIF on these topics. Building on their research collaborations, Dr. Magniez and he led an international student exchange program between Canada and a number of EU institutions, and a PICS project between the Institute for Quantum Computing at U. Waterloo and IRIF. Ashwin is looking forward to renewing these ties in the upcoming visit. edit all the past news (These news are displayed using a randomized-priority ranking.) Agenda Algorithms and complexity Tuesday October 15, 2024, 11AM, 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 Semantics Tuesday October 15, 2024, 3PM, 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 Tuesday October 15, 2024, 2PM, 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. Proofs, programs and systems Thursday October 17, 2024, 10:30AM, ENS Lyon Tba CHOCOLA seminar series Non-permanent members' seminar Thursday October 17, 2024, 4PM, 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. Higher categories, polygraphs and homotopy Friday October 18, 2024, 2PM, 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. Automata Friday October 18, 2024, 2PM, 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 Algorithms and complexity Tuesday October 22, 2024, 11AM, Salle 3052 Adam Wesolowski (Royal Holloway) Advances in quantum algorithms for the shortest path problem Enumerative and analytic combinatorics Thursday October 24, 2024, 2PM, 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. Proofs, programs and systems Thursday October 24, 2024, 10:30AM, Salle 3052 & online (Zoom link) Jean-Jacques Lévy To be announced.