Institut de Recherche en Informatique Fondamentale

Research Institute for Foundations of Computer Science

IRIF Université Paris 7 CNRS IRIF is a research laboratory co-founded by the CNRS and the University Paris-Diderot, resulting from the merging of the two research units LIAFA and PPS on January 1st, 2016.

The scientific objectives of the laboratory are at the core of computer science, focusing on: the mathematical foundations of computer science; computational models and proofs; models, algorithms and system design.

Upcoming seminars

Mardi 25 avril 2017 · 11h00 · Salle 1007

Algorithmes et complexité · Nicolas Flammarion (DI/ENS) · Optimal rates for Least-Squares Regression through stochastic gradient descent.

At a broad level, stochastic optimization is concerned with optimizing a function in the presence of noise. In this context, we consider the optimization of a quadratic objective function whose gradients are only accessible through a stochastic oracle that returns the gradient at any given point plus a zero-mean finite variance random error. We present the first algorithm that achieves the optimal prediction error rates for least-squares regression, both in terms of forgetting of initial conditions in O(1/n^2), and in terms of dependence on the noise and dimension d of the problem, as O(d/n). Our new algorithm is based on averaged accelerated regularized gradient descent, and may also be analyzed through finer assumptions on initial conditions and the Hessian matrix, leading to dimension-free quantities that may still be small while the “optimal” terms above are large.

Mardi 25 avril 2017 · 14h00 · Salle 1007

Algorithmique distribuée et graphes · Mike Molloy (University of Toronto and Ecole Normale Superieure Paris) · Entropy Compression and the Lovasz Local Lemma

The Lovasz Local Lemma, a cornerstone of the probabilistic method, is a powerful and widely used proof technique. In 2009, Moser introduced a technique called entropy compression to provide efficient algorithms which construct objects that the Local Lemma guarantees to exist. Recently, entropy compression has been used to develop more powerful versions of the Local Lemma which provide existence proofs in settings where the original Local Lemma does not apply. I will illustrate this technique with applications to graph colouring: (a) colouring triangle-free graphs, and (b) frugal colouring, where no colour can appear too many times in any neighbourhood.

Jeudi 27 avril 2017 · 10h30 · Salle 3052

Preuves, programmes et systèmes · Bérénice Delcroix-Oger (Institut de Mathématiques de Toulouse) · Des arbres sans ambiguités

Les tableaux boisés sont des objets combinatoires intervenant notamment dans l'étude de certains modèles de mécanique statistique. Cet exposé porte sur les arbres non ambigus, qui sont un cas particulier de tableaux boisés reliés aux permutations ayant leurs excédences (w(i)>i) en début de mot. Nous avons obtenu, lors d'un travail commun avec J.-C. Aval, A. Boussicault, F. Hivert et P. Laborde-Zubieta, des résultats énumératifs et bijectifs sur ces objets, que je présenterai ici après avoir introduit le cadre de cette étude.

Jeudi 27 avril 2017 · 10h30 · Salle 3052

Combinatoire énumérative et analytique · Bérénice Delcroix-Oger (IMT) · Des arbres sans ambiguités

Jeudi 27 avril 2017 · 14h00 · Salle 3052

Preuves, programmes et systèmes · Jeremy Siek (Indiana University) · The state of the art in gradual typing

Gradual typing is an approach for designing programming languages that integrate static and dynamic type checking. Gradual typing gives the programmer fine-grained control over which regions of a program are statically checked and which regions are dynamically checked. Over the last decade, there has been renewed interest in such an integration partly due to the rise in popularity of dynamic languages. But as small programs grow into large programs, so does the need for early error detection and modularity, which is provided by static type checking. Gradual typing provides a practical migration path for dynamically typed programs to become more statically typed. This talk will give a glimpse at the state of the art in gradual typing. It will describe a) the major challenges in the design and implementation of gradually typed languages, b) the research that has addressed many of of these challenges, and c) the open problems that need to be solved. The research in gradual typing spans both theoretical and practical questions, from mechanized metatheory to efficient compilation.

Vendredi 28 avril 2017 · 14h00 · Salle 1007

Catégories supérieures, polygraphes et homotopie · Martin Szyld · A general limit lifting theorem for 2-dimensional monad theory