Institut de Recherche en Informatique Fondamentale(IRIF)


image/svg+xml

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.

Miklós Santha

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.

Geoffroy Couteau

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.

Adrian Vladu

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.

Liat Peterfreund

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.

IRIF

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.

Thomas Vidick

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.

(These news are displayed using a randomized-priority ranking.)

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.