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. 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. 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. 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. edit all the past news (These news are displayed using a randomized-priority ranking.) Events 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) Verification Monday November 2, 2020, 11AM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ber-rxi-tol-i7y Damien Busatto (Université Libre de Bruxelles) Monte Carlo Tree Search guided by Symbolic Advice for MDPs We consider the online computation of a strategy that aims at optimizing the expected average reward in a Markov decision process. The strategy is computed with a receding horizon and using Monte Carlo tree search (MCTS). We augment the MCTS algorithm with the notion of symbolic advice, and show that its classical theoretical guarantees are maintained. Symbolic advice are used to bias the selection and simulation strategies of MCTS. We describe how to use QBF and SAT solvers to implement symbolic advice in an efficient way. We illustrate our new algorithm using the popular game Pac-Man and show that the performances of our algorithm exceed those of plain MCTS as well as the performances of human players. Proofs, programs and systems Thursday November 5, 2020, 10:30AM, Online Robin Piedeleu (University College London) To be announced. Automata Friday November 6, 2020, 2:30PM, Salle 3052 Denis Kuperberg (LIP, ENS Lyon, CNRS) Recognizing Good-for-Games automata: the G2 conjecture In the setting of regular languages of infinite words, Good-for-Games (GFG) automata can be seen as an intermediate formalism between determinism and nondeterminism, with advantages from both worlds. Indeed, like deterministic automata, GFG automata enjoy good compositional properties (useful for solving games and composing automata and trees) and easy inclusion checks. Like nondeterministic automata, they can be exponentially more succinct than deterministic automata. I will focus in this talk on the following problem: given a nondeterministic parity automaton on infinite words, is it GFG ? The complexity of this problem is one of the main remaining open questions concerning GFG automata, motivated by the potential applications that would come with an efficient algorithm. After giving the necessary context, I will explain the current understanding on this question, and describe a simple polynomial-time algorithm that is conjectured to solve the problem, but has only been proven correct if the input is a Büchi or a co-Büchi automaton.