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 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. 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. 8.10.2019 From ancient history to quantum, learn about cryptography at “Fête de la science” in an entertaining talk by Sylvain Perifel (IRIF) Friday October 11th, 11am at Amphitheater 4C, Halle aux farines. 2.10.2019 IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Hugo Férée, an expert in various aspects of complexity theory, with interests in programming languages and formal proofs. 8.10.2019 The SODA 2020 conference will include a paper by Vincent Cohen-Addad (LIP6), Frederick Mallmann-Trenn (King's College) and Claire Mathieu (IRIF) about computing with noisy data. The problem: select valuable objects in a setting where each assessment has a probability of error, using redundant assessments. 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 Researchers of IRIF are participating in the “Fête de la Science”! Meet them at the University of Paris October 10-11 to better understand the first principles of computing! 1.10.2019 IRIF has the great pleasure to welcome a new research scientist (CNRS): Geoffroy Couteau, an expert in cryptography, with a focus on secure computation protocols and zero-knowledge proofs. edit all the past news (These news are displayed using a randomized-priority ranking.) Events Algorithms and complexity Tuesday October 15, 2019, 11AM, Salle 1007 Zvi Lotker (Ben Gurion University) Variation on preferential-attachment In this talk, I will describe how preferential attachment arises from the first principle using game theory. Next, I will extend the model of preferential attachment into a general model, which allows for the incorporation of Homophily ties in the network. This talk is based on joint works with Prof. Chen Avin, Avi Cohen, Yinon Nahum, Prof. Pierre Fraigniaud, and Prof. David Peleg. Enumerative and analytic combinatorics Thursday October 17, 2019, 2PM, Salle 1007 Mark Skandera (Lehigh university) Non négativité et traces de l'algèbre de Hecke La recherche de Gantmacher sur les matrices totalement non négatives dans les années 1930 - 1940 a influencé plusieurs domaines des mathématiques. Par exemple, nous avons les polynômes totalement non négatifs, ces polynômes en n^2 variables dont l'évaluation sur chaque matrice totalement non négative est un nombre non négatif. Ces polynômes sont liés à certaines traces de l'algèbre de Hecke dont les évaluations sur certaines éléments de la base de Kazhdan-Lusztig sont des polynômes dans N[q]. Dans tous les cas, il serait intéressant d'interpréter de manière combinatoire les entiers non négatifs qui apparaissent dans les évaluations. Nous verrons un nouveau résultat sur certaines traces qui améliore notre compréhension des polynômes non négatifs. Ce travaille a été réalisé avec Adam Clearwater. Proofs, programs and systems Thursday October 17, 2019, 10:30AM, École normale supérieure de Lyon Eric Finster Séminaire Chocola http://chocola.ens-lyon.fr/events/ Higher categories, polygraphs and homotopy Friday October 18, 2019, 2PM, Salle 1007 Léonard Guetta (IRIF) Colimites homotopiques et tranches Verification Monday October 21, 2019, 11AM, Salle 1007 Mohamed Faouzi Atig (Uppsala University) On Solving String Constraints String data types are present in all conventional programming and scripting languages. In fact, it is almost impossible to reason about the correctness and security of such programs without having a decision procedure for string constraints. A typical string constraint consists of word equations over string variables denoting strings of arbitrary lengths, together with constraints on (i) the length of strings, and (ii) the regular languages to which strings belong. Decidability of this general logic is still open. In this talk, we will discuss recent results on the decidability and decision procedures for string constraints. We will focus on decision procedures that are sound and complete for a well-defined fragment of string constraints. We will also cover a technique that uses a Counter-Example Guided Abstraction Refinement (CEGAR) framework which contains both an under- and an over-approximation module. The flow of information between these modules allows increasing the precision in an automatic manner. 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.