Welcome to IRIF 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. More People Contact Follow @IRIF_Paris Notion of the day News 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. 11.6.2019 Kamil Khadiev from Kazan University, an expert in complexity and quantum computing, is visiting IRIF from June 10th to July 9th. 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. 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). edit all the news (These news are displayed using a randomized-priority ranking.) Events Enumerative and analytic combinatorics Thursday June 20, 2019, 11:45AM, Salle 1007 Vincent Jugé (Université Paris-Est Marne-la-Vallée) To be announced. Proofs, programs and systems Thursday June 20, 2019, 10:30AM, Salle 3052 Alex Simpson (University of Ljubljana) Sheaf principles for reasoning about probabilistic independence 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. PhD defences Friday June 21, 2019, 3PM, Amphithéâtre Turing Nikola K. Blanchard (IRIF) Usability: low tech, high security The manuscript is available at: http://koliaza.com/files/thesis_blanchard_nikola_k.pdf 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.