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), five 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 16.10.2019 On December 16th, a half-day of talks aimed at a non-specialized audience will take place at IRIF in celebration of Algorithms, the research domain of Claire Mathieu, 2019 recipient of a CNRS Silver Medal. The event will conclude with a discussion of new research directions in Algorithms. Free Registration before November 30th. 10.9.2019 IRIF is seeking excellent candidates for about 10 postdoctoral positions in all areas of the Foundations of Computer Science. Deadline for applications: Nov. 3, 2019. 24.9.2019 IRIF has the great pleasure to welcome a new professor (Université de Paris): Sylvain Schmitz, an expert in logic and verification, and especially in problems of astronomical computational complexity. 25.9.2019 IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Sam Van Gool, an expert in algebraic and topological methods for automata, logic, and model theory. 23.9.2019 Giuseppe Castagna (IRIF) and Jeremy Siek (Indiana) organize WGT 2020, the first ACM SIGPLAN Workshop on Gradual Typing, colocated with POPL. Submission deadline: Monday, October the 21st. gradual typing Gradual typing is a technique that allows the programmer to control which parts of a program check their type correctness (i.e., that apples are added to apples) before execution and which parts check it during their execution instead. It is often used to gradually add the before-execution check to dynamic languages, like JavaScript, which perform the check only at run-time, since it is generally better to find errors before the execution of a program rather than during its execution. 3.9.2019 IRIF has the great pleasure to welcome Leonid Libkin, professor at University of Edinburgh, who is visiting for three months. His stay is financed by an FSMP chair. Leonid is an expert in data management and applications of logic in computer science. Meet him in office 4048. 8.10.2019 Talks of the IRIF Distinguished Talks Series for the coming academic year have been scheduled. Save the dates: January 24, March 20 and June 20. Speakers will be Martin Grohe (RWTH Aachen University), Joseph Mitchell (State University of New York at Stony Brook), Simon Peyton Jones (Microsoft Research at Cambridge, England). 25.9.2019 Three papers coauthored by IRIF members will be presented at SODA’20, the main conference in algorithm design. Topics include the study of noisy models, aggregate rankings, and graph diameters. edit all the past news (These news are displayed using a randomized-priority ranking.) Events Graphs Tuesday October 22, 2019, 2PM, Salle 3052 Michael Lampis (Universite Paris Dauphine) Finer Tight Bounds for Coloring on Clique-Width We revisit the complexity of Coloring with respect to two parameters: the number of given colors k; and the “width” of the input graph w. Here, by width we mean a measure of complexity of the graph. When the notion of width in question is treewidth, the problem is very well-understood: there exists a simple k^w algorithm, and no algorithm can do significantly better under the Strong Exponential Time Hypothesis (SETH), even if we replace treewidth by much more restrictive notions, such distance to linear forest. In this talk we will consider the notion of clique-width, which is the most well-studied generalization of treewidth for dense graphs. We will sketch an algorithm and a matching lower bound (under the SETH) which completely determine the complexity of coloring as a function of clique-width, for any fixed k>=3. Special talks Tuesday October 22, 2019, 7PM, 3052 Hao Huang (Emory University) A proof of the Sensitivity Conjecture. (live projection of TCS+ talk) This is a live video projection of a TCS+ talk. Live questions should be possible. IRIF Cake Thursday October 24, 2019, 5PM, In front of room 3052 Cédric Ho Thanh (IRIF CakeTM) Gâteau de l'IRIF IRIF CakeTM is an amazing opportunity to meet people while simultaneously eating cakes baked by your fellow colleagues! Join us every Thursday, at 5pm, in front of room 3052 (Sophie Germain 3rd floor) for a weekly feast. You can also express your cooking skills and volunteer to bake a cake by sending an email to cake@irif.fr. Automata Friday October 25, 2019, 2:30PM, Salle 3052 Luca Reggio (Mathematical Institute, University of Bern) Limits of finite structures: a duality theoretic perspective A systematic approach to the study of limits of finite structures, motivated by investigations in graph theory, has been developed by Nešetřil and Ossona de Mendez starting in 2012. The basic idea consists in embedding the set of finite structures into a space of measures which is complete, so that every converging sequence of finite structures admits a limit. This limit point can be always realized as a measure. I will explain how this embedding into a space of measures dually corresponds to enriching First-Order Logic with certain probability operators. Further, I will relate this construction to first-order quantification in logic on words. This talk is based on joint work with M. Gehrke and T. Jakl. Automata Monday October 28, 2019, 11AM, Salle 1007 Pierre Ganty (IMDEA Software Institute) Deciding language inclusion problems using quasiorders We study the language inclusion problem L1 ⊆ L2 where L1 is regular or context-free. Our approach checks whether an overapproximation of L1 is included in L2. Such overapproximations are obtained using quasiorder relations on words where the abstraction gives the language of all words “greater than or equal to” a given input word for that quasiorder. We put forward a range of quasiorders that allow us to systematically design decision procedures for different language inclusion problems such as context-free languages into regular languages and regular languages into trace sets of one-counter nets. Verification Monday October 28, 2019, 11AM, Salle 1007 Pierre Ganty (IMDEA Software Institute) Deciding language inclusion problems using quasiorders We study the language inclusion problem L1 ⊆ L2 where L1 is regular or context-free. Our approach checks whether an overapproximation of L1 is included in L2. Such overapproximations are obtained using quasiorder relations on words where the abstraction gives the language of all words “greater than or equal to” a given input word for that quasiorder. We put forward a range of quasiorders that allow us to systematically design decision procedures for different language inclusion problems such as context-free languages into regular languages and regular languages into trace sets of one-counter nets.