image/svg+xml Welcome IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and Université de Paris, also hosting two Inria project-teams. 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. Six of its members have been distinguished by the European Research Council (ERC), five 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. More People Contact Follow @IRIF_Paris Notion of the day News 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. 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. 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. 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. 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. 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. edit all the past news (These news are displayed using a randomized-priority ranking.) Events Proofs, programs and systems Thursday October 29, 2020, 4PM, Online Jan Hoffmann (Carnegie Mellon University) To be announced. Automata Friday October 30, 2020, 2:30PM, 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)