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 deux équipes-projets 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. Présentation Annuaire Contacts Suivre @IRIF_Paris Notion du jour Actualités 15.10.2020 Liat Peterfreund (former IRIF postdoc, 2019-20) is one of the recipients of the L'Oréal-Unesco award for women in science. Liat is studying the science of data processing: how to extract data, how to classify it and, above all, how to make it meaningful. 21.10.2020 A paper by Troy Lee, Miklós Santha (IRIF CNRS member), and Shengyu Zhang on quantum algorithms for graph problems with cut queries will be presented at SODA2021. 21.10.2020 A paper by E. Boyle, G. Couteau (IRIF CNRS researcher), N. Gilboa, Y. Ishai, L. Kohl and P. Scholl has been resented at the conference CRYPTO2020 on how to securely generate bounded amounts of correlated randomness. 2.10.2020 IRIF is seeking excellent candidates for about 10 postdoctoral positions in all areas of the foundations of Computer Science. Deadline for applications: Nov. 2, 2020. 18.8.2020 IRIF is very pleased to host for 12 months starting in September 2020, Thomas Vidick, professor of computer science and mathematics at the California Institute of Technology. His research is at the interface of theoretical computer science, quantum information and cryptography. The invitation is funded by an FSMP chair together with DIENS, Inria and IRIF. Meet him in office 4024. 1.10.2020 IRIF has the great pleasure to welcome a new research scientist (CNRS): Adrian Vladu, an expert in continuous optimization, which he uses to develop improved algorithms for combinatorial problems and methods for machine learning. 30.9.2020 This year's PPS days will take place online on October 1, 8, and 15, each time between 10:20 and 12:30. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Événements Algorithmes et complexité Mercredi 28 octobre 2020, 11 heures, Salle 3052 & En ligne Simon Mauras (IRIF) Assessment of Covid-19 containment strategies in primary schools and workplaces using contact graphs I will explain how modelling the epidemic using graphs could help in reopening strategies. This work has been done in collaboration with Guillaume Duboc, Max Dupré la Tour, Paolo Frasca, Claire Mathieu, Lulla Opatowski and Laurent Viennot. Preuves, programmes et systèmes Jeudi 29 octobre 2020, 15 heures, Online at https://crocus.irif.fr:8443/group/seminaire-pps Jan Hoffmann (Carnegie Mellon University) Raising Expectations: Automating Expected Cost Analysis with Types In a recent article, my students and I have introduced a type-based analysis for deriving upper bounds on the expected execution cost of functional probabilistic programs. The analysis is naturally compositional, parametric in the cost model, and supports higher-order functions and inductive data types. The derived bounds are multivariate polynomials that are functions of data structures. Bound inference is enabled by local type rules that reduce type inference to linear constraint solving. The type system is based on the potential method of amortized analysis and extends automatic amortized resource analysis (AARA) for deterministic programs. In this talk, I will first give an overview of AARA for deterministic programs and some of the innovations that have been introduced over the past decade. I will then describe our novel results on expected bound analysis for probabilistic programs, highlight the challenges of adopting AARA to a probabilistic language, present experimental results, and discuss some open problems. Automates Vendredi 30 octobre 2020, 14 heures 30, Salle 3052 Wojciech Czerwiński (University of Warsaw) Universality problem for unambiguous Vector Addition Systems with States I will show that the universality problem is ExpSpace-complete for unambiguous VASS, which is in strong contrast with Ackermann-completeness of the same problem for nondeterministic VASS. I also plan to present some more results concerning the interplay between unambiguity and VASS. (joint work with Diego Figueira and Piotr Hofman)