Les membres de l'IRIF et les visiteurs sont priés de se conformer aux directives COVID-19 du CNRS et de l'Université de Paris. image/svg+xml Bienvenue L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université de Paris, qui 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. Six de ses membres ont été lauréats de l'European Research Council (ERC), cinq 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. Tweets by IRIF_Paris Notion du jour Actualités 29.4.2021 The Annual meeting of ANR-HOSIGRA, in collaboration with teams from India and China, will take place online May 3-6. The schedule of the talks is available here. Find abstracts and the zoom link here. 29.4.2021 IRIF will finance one or two additional Master scholarships in Foundations of Computer Science within the PGSM program of FSMP for female students who have completed a bachelor’s degree or the first year masters in one of the universities of the FSMP network. Apply online by May 8th. 9.4.2021 We are happy to welcome Mirna DŽAMONJA, winner of an individual grant Marie CURIE part of the H2020 European program. Learn more about her and her work here 22.4.2021 Sylvain Perifel (IRIF) and Guillaume Lagarde (Université de Bordeaux) publish on the Blog Binaire the first article of a series about algorithmic complexity. The series aims be easy-to-understand and accessible to everyone. 23.4.2021 Six papers coauthored by IRIF members will be presented at the prestigious conference LICS'21 this summer. Topics include game semantics, linear logic, categorical models, type theory and rewriting systems. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Événements Automates Vendredi 7 mai 2021, 14 heures 30, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl Sadegh Soudjani On Decidability of Time-Bounded Reachability in CTMDPs In this talk, I discuss the time-bounded reachability problem for continuous-time Markov decision processes. I show that the problem is decidable subject to Schanuel’s conjecture. The decision procedure relies on the structure of optimal policies and the conditional decidability (under Schanuel’s conjecture) of the theory of reals extended with exponential and trigonometric functions over bounded domains. I further discuss that any unconditional decidability result would imply unconditional decidability of the bounded continuous Skolem problem, or equivalently, the problem of checking if an exponential polynomial has a non-tangential zero in a bounded interval. The latter problems are also decidable subject to Schanuel’s conjecture but finding unconditional decision procedures remain longstanding open problems. Time permitting, I can also discuss some algorithmic approximate computations using Lyapunov theory of dynamical systems. This talk is based on an ICALP 2020 paper joint with Rupak Majumdar and Mahmoud Salamati at MPI-SWS. Graph Transformation Theory and Applications Vendredi 7 mai 2021, 15 heures, online James Fairbanks (Department of Computer & Information Science & Engineering, University of Florida, USA) Computational Categorical Algebra with Catlab A vast swath of computation and computer science theory takes place on combinatorial data structures, which are often presented as variations on the theme of graphs. Catlab.jl is a Julia package for computational category theory, which includes an implementation of C-Sets, also known as copresheafs or category actions. C-Sets always form an adhesive category and can be used for general rewriting systems. This talk will present the theory and implementation of C-Sets along with some examples. In particular, Colored Graphs and String Diagrams (syntax for symmetric monoidal categories) will be shown. Zoom registration YouTube live stream Vérification Lundi 10 mai 2021, 11 heures, BBB link Laurent Doyen (LMF — ENS Saclay) Observation and Distinction. Representing Information in Infinite Games We compare two approaches for modelling imperfect information in infinite games by using finite-state automata. The first, more standard approach views information as the result of an observation process driven by a sequential Mealy machine. In contrast, the second approach features indistinguishability relations described by synchronous two-tape automata. The indistinguishability-relation model turns out to be strictly more expressive than the one based on observations. We present a characterisation of the indistinguishability relations that admit a representation as a finite-state observation function. We show that the characterisation is decidable, and give a procedure to construct a corresponding Mealy machine whenever one exists. The talk is based on joint work with Dietmar Berwanger. Algorithmique distribuée et graphes Mardi 11 mai 2021, 14 heures, ZOOM Bérénice Delcroix-Oger Parking trees In 1980, Edelman defined a poset on objects called noncrossing 2-partitions, made of a partition and a noncrossing partition, with a bijection linking parts of the same size in both partitions. Studying this poset, he proved that the number of noncrossing 2-partitions is given by (n+1)^{n-1}. This is also the number of classical combinatorial objects called parking functions. After introducing noncrossing partitions, noncrossing 2-partitions and parking functions, we will draw the link between parking functions and noncrossing 2-partitions, describing Edelman's poset in terms of parking functions. Afterwards, we will (recall and) use the notion of species introduced in the early 1980s by Joyal to describe the action of the symmetric group on a poset on parking trees. This is a joint work with Matthieu Josuat-Vergès and Lucas Randazzo. Soutenances de thèses Mardi 11 mai 2021, 15 heures, Online Yixin Shen (IRIF) Classical and quantum cryptanalysis for Euclidean lattices and subset sum Post-quantum cryptography is a branch of cryptography that aims at designing non-quantum (i.e. classical) cryptographic systems, which are protected against an adversary possessing a quantum computer. In this thesis, we focus on the study of two fundamental problems for post-quantum cryptography: the shortest vector problem (SVP) and the random subset sum problem. We propose several classical/quantum algorithms that improve the state of the art. One world numeration seminar Mardi 11 mai 2021, 14 heures 30, Online Giulio Tiozzo (University of Toronto) The bifurcation locus for numbers of bounded type We define a family B(t) of compact subsets of the unit interval which provides a filtration of the set of numbers whose continued fraction expansion has bounded digits. This generalizes to a continuous family the well-known sets of numbers whose continued fraction expansion is bounded above by a fixed integer. We study how the set B(t) changes as the parameter t ranges in [0,1], and describe precisely the bifurcations that occur as the parameters change. Further, we discuss continuity properties of the Hausdorff dimension of B(t) and its regularity. Finally, we establish a precise correspondence between these bifurcations and the bifurcations for the classical family of real quadratic polynomials. Joint with C. Carminati. Algorithmes et complexité Mercredi 12 mai 2021, 10 heures, Collège de France Frédéric Magniez - Miklos Santha (IRIF - CNRS, CQT) Transformée de Fourier quantique I Quatrième cours de Frédéric Magniez au Collège de France sur les Algorithmes quantiques (à 10h), suivi d'un exposé de Miklos Santha sur « Le problème du sous-groupe caché » (à 11h30). Informations supplémentaires : https://www.college-de-france.fr/site/frederic-magniez/course-2021-05-12-10h00.htm Théorie des types et réalisabilité Mercredi 12 mai 2021, 14 heures, online (https://bbb-front.math.univ-paris-diderot.fr/recherche/hug-a7x-lga-hy7) Félix Castro (IRIF) Proving Church Thesis in Heyting Arithmetic with Lisp's quote Preuves, programmes et systèmes Jeudi 13 mai 2021, 16 heures, Online at link (any password works) Carlo Angiuli (Carnegie Mellon University) Internalizing Representation Independence with Univalence Automates Vendredi 14 mai 2021, 14 heures 30, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl Charles Paperman Non encore annoncé.