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.

Workshop on Gradual Typing

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.

Sylvain Perifel

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.

Hugo Férée

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.

Claire Mathieu

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.

Leonid Libkin

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.

IRIF

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!

Geoffroy Couteau

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.

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

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

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.