IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and université Paris-Diderot, 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), three are members of the Institut Universitaire de France IUF), and two are members of the Academia Europæa.

Kamil Khadiev

11.6.2019
Kamil Khadiev from Kazan University, an expert in complexity and quantum computing, is visiting IRIF from June 10th to July 9th.

CIMPA

23.1.2019
A CIMPA school on Graphs, Algorithms and Randomness is co-organized by Reza Naserasr from IRIF at Tabriz University, 15-22 June 2019. Three colleagues from IRIF, Pierre Fraigniaud, Michel Habib and Frédéric Magniez, are among the five lecturers from France.

perso-mikael-rabie.jpg

25.5.2019
Mikaël Rabie (Postdoc at IRIF) will present at ICALP'19 a new problem, about distributed reconfiguration of maximal independent sets, providing an optimal algorithm to produce a reconfiguration schedule in the LOCAL model. This work, receiving Best Paper award in Track C, is a joint work with Keren Censor-Hillel from the Technion (Haifa, Israël).

Conference CAV'19

30.5.2019
Four papers coauthored by IRIF members will be presented at the prestigious conference CAV'19 in New York this summer. Topics include verifying weakly-consistent distributed databases, testing cache coherence protocols, and testing concurrent objects.

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

Habilitation defences
Tuesday June 18, 2019, 10AM, Salle des Thèses, Halle aux Farines
Yves Guiraud Méthodes de réécriture en algèbre supérieure

Proofs, programs and systems
Wednesday June 19, 2019, 2:30PM, Salle 3052
Ugo Dal Lago (INRIA and Univ. Bologna) The Geometry of Bayesian Programming

We give a geometry of interaction model for a typed lambda-calculus endowed with operators for sampling from a continuous uniform distribution and soft conditioning, namely a paradigmatic calculus for higher-order Bayesian programming. The model is based on the category of measurable spaces and partial measurable functions, and is proved adequate with respect to both a distribution-based and a sampling based operational semantics.

Joint work with Naohiko Hoshino

Enumerative and analytic combinatorics
Thursday June 20, 2019, 11:45AM, Salle 1007
Vincent Jugé (Université Paris-Est Marne-la-Vallée) To be announced.

PhD defences
Thursday June 20, 2019, 2:30PM, Salle 0011
Raphaëlle Crubillé (IRIF) Behavioural distances for higher-order probabilistic programs

The manuscript is available at: http://research.crubille.lautre.net/main.pdf

Higher categories, polygraphs and homotopy
Friday June 21, 2019, 2PM, Salle 1007
Alain Prouté Qu'est-ce qu'un ensemble ?

Si, il y a 10.000 ans, il y avait un mot pour désigner un troupeau de moutons, ce mot voulait aussi dire «ensemble», même si cette notion d'ensemble était moins abstraite que celle que Bolzano, Dedekind et Cantor introduisirent à la fin du XIXe siècle. On pourrait croire qu'après la théorie des ensembles de Zermelo et Fraenkel, la question de savoir ce qu'est un ensemble était close. Ce n'est pas le cas comme le remarque par exemple Quine, auteur d'une théorie alternative, qui dit dans les années 60 que la question est toujours ouverte. Une nouvelle impulsion sera donnée par Lawvere avec sa théorie axiomatique de la catégorie des ensembles, et surtout par Lawvere et Tierney avec la notion de topos élémentaire. Cette dernière notion inspirera Volger, puis Lambek, qui définira la notion de «dogme». J'ai rebaptisé leur théorie en «théorie des ensembles de Volger-Lambek». J'en donnerai une description et j'expliquerai pourquoi elle est, à condition qu'elle soit un peu généralisée, la bonne théorie de formalisation non seulement des ensembles, mais de toute la mathématique telle que nous la pratiquons aujourd'hui.

Enumerative and analytic combinatorics
Monday June 24, 2019, 11AM, Salle 3052
Carola Doerr (CNRS, LIP6 Sorbonne University) Evolutionary Algorithms – From Theory to Practice and Back

Most real-world optimization problems do not have an explicit problem formulation, but only allow to compute the quality of selected solution candidates. Solving such black-box optimization problems requires iterative procedures which use the feedback gained from previous evaluations to determine the strategy by which the next solution candidates are generated. Many black-box optimization algorithms, such as Simulated Annealing, Evolutionary Algorithms, Swarm Intelligence Algorithms, are randomized – making it very difficult to analyze their performances mathematically.

In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations.

In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.

Algorithms and complexity
Monday June 24, 2019, 11AM, Salle 3052
Carola Doerr (CNRS, LIP6 Sorbonne University) Evolutionary Algorithms – From Theory to Practice and Back

Most real-world optimization problems do not have an explicit problem formulation, but only allow to compute the quality of selected solution candidates. Solving such black-box optimization problems requires iterative procedures which use the feedback gained from previous evaluations to determine the strategy by which the next solution candidates are generated. Many black-box optimization algorithms, such as Simulated Annealing, Evolutionary Algorithms, Swarm Intelligence Algorithms, are randomized – making it very difficult to analyze their performances mathematically.

In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations.

In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.

Complex systems
Monday June 24, 2019, 11AM, Salle 3052
Carola Doerr (CNRS, LIP6 Sorbonne University) Evolutionary Algorithms – From Theory to Practice and Back

Most real-world optimization problems do not have an explicit problem formulation, but only allow to compute the quality of selected solution candidates. Solving such black-box optimization problems requires iterative procedures which use the feedback gained from previous evaluations to determine the strategy by which the next solution candidates are generated. Many black-box optimization algorithms, such as Simulated Annealing, Evolutionary Algorithms, Swarm Intelligence Algorithms, are randomized – making it very difficult to analyze their performances mathematically.

In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations.

In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.

Graphs
Monday June 24, 2019, 11AM, Salle 3052
Carola Doerr (CNRS, LIP6 Sorbonne University) Evolutionary Algorithms – From Theory to Practice and Back

Most real-world optimization problems do not have an explicit problem formulation, but only allow to compute the quality of selected solution candidates. Solving such black-box optimization problems requires iterative procedures which use the feedback gained from previous evaluations to determine the strategy by which the next solution candidates are generated. Many black-box optimization algorithms, such as Simulated Annealing, Evolutionary Algorithms, Swarm Intelligence Algorithms, are randomized – making it very difficult to analyze their performances mathematically.

In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations.

In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.