Laboratoire d'informatique de l'École polytechnique


Grand prix Huy Duong Bui de l’Académie des sciences décerné à Bernadette Charron-Bost

Bernadette Charron-Bost, directrice de recherche du CNRS a reçu le 15 octobre 2019 le Grand prix Huy Duong Bui de l’Académie des sciences :

Lire l'article sur le site de l'Ecole Polytechnique

Voir la page sur le site de l'Académie des Sciences

Soutenance de thèse d'Ulysse Gérard (Parsifal)

Speaker: Ulysse Gérard
Location: Amphi Sophie Germain
Date: Ven. 18 oct. 2019, 14h00-16h00

Ulysse Gérard soutiendra sa thès, intitulée «Calculer avec des relations, des fonctions et des lieurs», le 18 octobre 2019 à 14h00, dans l'amphithéâtre Sophie Germain du bâtiment Alan Turing.

Exposé par N. Bergeron: «Bounded P-partition and Flagged P-partition»

Speaker: Nantel Bergeron
Location: Salle Philippe Flajolet
Date: Wed, 16 Oct 2019, 11:00-12:00

Pour le prochain séminaire de Combinatoire du Plateau de Saclay, nous aurons le plaisir d'écouter Nantel Bergeron (York University, et professeur invité par la DER) nous parler de Bounded P-partition and Flagged P-partition, travaux en commun avec Sami Assaf.

Le programme du séminaire est disponible ici :

Talk by Michael Gnewuch: «On Negative Dependence Properties of Sampling Schemes and Probabilistic Discrepancy Bounds»

Speaker: Michael Gnewuch
Location: Room Henri Poincaré, Alan Turing building
Date: Mon, 14 Oct 2019, 14:00-15:00

On Monday, October 14th, at 2pm, in Salle Poincaré, Michael Gnewuch (U. Osnabrück) will give a talk entitled: On Negative Dependence Properties of Sampling Schemes and Probabilistic Discrepancy Bounds.

Abstract: In several problems as, e.g., numerical integration or one-shot optimization, one is interested in having sample points that are uniformly distributed and have certain additional nice features, as, e.g, very regular low-dimensional projections. As a measure of uniformity of distribution we consider the star discrepancy. Especially in high dimension, Monte Carlo points exhibit good uniform distribution properties, but will usually not exhibit the additional nice features one is interested in. In this talk we present a relaxed notion of negative orthant dependence that still allows for large deviation bounds. We present a theorem stating that sample points that satisfy this notion have a small star discrepancy that is at least as good (or only slightly worse) than the one of Monte Carlo points. The hope is that this class of sample point sets contains sets that have the desired additional features.The notion is, for instance, satisfied by Latin hypercube samples. We show that a relaxation of the notion of negative orthant dependence is essential, otherwise the theorem cannot be applied to Latin hypercube sampling or to so-called (t, m, s)-nets.

Talk by Gurprit Singh: «How to Train Your Samples?»

Speaker: Gurprit Singh
Location: Room Henri Poincaré (ground floor)
Date: Mon, 30 Sep 2019, 14:00-15:00

Gurprit Singh from MPI will visit the Stream team next Monday and will give a talk entitled: How to Train Your Samples?

Abstract: Samples are the basic building block in many domains including computer graphics/vision and financial mathematics. In this talk, we will see how sample correlations play a crucial role in many areas including denoising, geometry reconstruction from point clouds, object placement and variance reduction during Monte Carlo integration for rendering. We briefly also touch upon the effectiveness of different sample shapes like points, segments and lines and look at different spatial and spectral tools that can be used to analyze sample correlations.

In the later part, I will present modern deep learning pipeline to generate these sample correlations in multiple dimensions. We show how--without any training data--a neural network can optimize correlations that were not possible to conceive earlier in a straight forward manner. The simplicity and expressivity of our architecture makes the tedious and mathematically involved pattern generation tasks a thing of the past.

Bio: Gurprit Singh is a senior researcher, leading the sampling and rendering group at the Max Planck Institute for Informatics (MPII), Saarburcken, Germany. He did his PhD from Université de Lyon 1, France, in 2015. This was followed by a postdoc at Dartmouth College, USA, with another two-year postdoc at MPII Saarbrucken, before he accepted the senior researcher position at MPII. His group focuses on understanding and synthesizing sample correlations for variance reduction in Monte Carlo and Quasi-Monte Carlo integration problems with direct application for image synthesis. He uses both theoretical and deep learning based tools to gain further understanding of how nature encodes correlations in objects that revolves around us.

Talk by Nathalie Aubrun (at LRI): «The Domino Problem is undecidable on surface groups»

Speaker: Nathalie Aubrun (ENS Lyon)
Location: Room 445, LRI
Date: Fri, 27 Sep 2019, 14:30-15:30

The next algorithmic seminar of the Saclay plateau will take place on Friday, September 27 at 14:30 at LRI in room 445 (patio room). Nathalie Aubrun (ENS Lyon) will talk about The Domino Problem is undecidable on surface groups.

Abstract: The domino problem for a finitely generated group asks whether there exists an algorithm which takes as input a finite alphabet and finitely many Wang tiles, and decides whether there exists a tiling of the group by this set of tiles. I will survey known results and present the domino problem conjecture: finitely generated groups with decidable domino problem are exactly virtually free groups. Then I will explain why this problem is undecidable on surface groups. Joint work with Sebastián Barbieri and Etienne Moutot.

PhD Defense of Tien-Duc CAO: «Toward Automatic Fact-Checking of Statistic Claims»

Speaker: Tien-Duc Cao
Location: Room Gilles Kahn, LIX
Date: Thu, 26 Sep 2019, 14:30-16:30

Tein-Duc Cao, member of the Cedar team, will defend his PhD thesis, entitled: "Toward Automatic Fact-Checking of Statistic Claims".

The defense will take place on Thursday, September 26 at 2:30pm, in the conference room Gilles Kahn at INRIA Saclay (1 Rue Honoré d'Estienne d'Orves, 91120 Palaiseau).


Data journalism and journalistic fact-checking are areas of growing interest within the journalism community and also in the audience at large, given the recent interest in misinformation, manipulation through the media, and journalistic efforts to prevent and debunk such attempts.

This thesis has been developed within a collaboration between several research laboratories and Les Décodeurs, the fact-checking team of the Le Monde newspaper.

The thesis proposed an end-to-end approach toward the automated fact-checking of statistic claims on a topic covered by a reference (trusted) database. Specifically, we have first devised an approach for extracting Linked Open Data from the Web publications of INSEE, the leading french statistic institute. Second, we developed an original search algorithm which, given a set of keywords such as "unemployment rate France 2018", is capable of returning the datasets (and, if possible, the exact values within the datasets) deemed most relevant to the user keywords. Third, we have developed an approach for automatically identifying, in a text written in French, mentions of statistic entities, together with the values associated by the text to these entities, and other context terms (e.g., time or place) attached to the statistic claim. Together, these enable a semi-automated statistic claim verification pipeline, whereas claims are extracted automatically from text and a query is sent to our data retrival algorithm, which returns the reference information closest to the given query. A human user, e.g., a journalist, can then compare the data to the claimed value in order to interpret it in a fact-checking work.

This thesis has been carried on within the ANR ContentCheck project focused on models, algorithms and tools for data journalism and journalistic fact-checking (

Séminaire Combi: exposé par Stefan Felsner

Speaker: Stefan Felsner
Location: Salle Philippe Flajolet, LIX
Date: Wed, 25 Sep 2019, 10:30-11:30

Pour la reprise du séminaire nous aurons le plaisir d'écouter Stefan Felsner (TU Berlin) nous parler de "Improved bounds for centered colorings". Veuillez noter que l'exposé sera 30mn plus tôt que l'horaire habituel (toujours en salle Philippe Flajolet au LIX). Le résumé est disponible ci-dessous.

Le programme du séminaire est disponible ici :

Résumé: A vertex coloring ϕ of G is p-centered if for each connected subgraph H of G either ϕ uses more than p colors on H or there is a color that appears exactly once on H. Centered colorings form one of the families of parameters that allow to capture notions of sparsity of graphs: A class of graphs has bounded expansion if and only if there is a function f such that for every p > 1, every graph in the class admits a p-centered coloring using at most f(p) colors. In this paper, we give upper and lower bounds for the maximum number of colors needed in a p-centered coloring of graphs from several widely studied graph classes. This includes outerplanar graphs, planar graphs, graphs of bounded treewidth and graphs of bounded degree. Joint work with M. Debski, P. Micek, and F. Schroeder

Soutenance de thèse de Mathias Lepoutre

Speaker: Mathias Lepoutre
Location: Amphithéâtre Sophie Germain, Bâtiment Turing.
Date: Mar. 24 sept. 2019, 15h00-17h00

Mathias Lepoutre soutiendra sa thèse, intitulée «Bijection bourgeonnantes, multitriangulations, quid des autres surfaces?», le mardi 24 septembre, à 15h00 dans l'amphithéâtre Sophie Germain du bâtiment Turing.

Résumé : Les cartes combinatoires sont des dessins de graphes sur des surfaces. On propose une méthode bijective de découpage d'une carte sur une surface orientable ou non, en une carte décorée à une face. Ceci généralise le cas planaire proposé dans [Sch97]. La carte obtenue peut à son tour être décomposée successivement en cartes plus petites munies de décorations, ce qui permet de démontrer combinatoirement des résultats structurels tel que la rationalité paramétrique de la série des cartes d'une surface orientable donnée, qui avait été d'abord obtenue par le calcul dans [BenCan91,BenCanRic93]. Une k-triangulation d'un polygone est un ensemble maximal de diagonales, sans que k+1 diagonales se croisent 2 à 2. On cherche à étudier les k-triangulations d'une surface quelconque, et notamment la structure des k-étoiles qui la composent (en suivant les travaux de [PilSan07]. Notre méthode consiste à se ramener par le recouvrement universel au cas de k-triangulations infinies et périodiques.

Talk by Marvin Künnemann: «On Nondeterministic Derandomization of Freivalds' Algorithm»

Speaker: Marvin Künnemann
Location: room Philippe Flajolet (2017)
Date: Mon, 16 Sep 2019, 10:30-11:30

We will have the pleasure to hear a talk from Marvin Künnemann (Max-Planck Institute for Informatics) about Nondeterministic Derandomization of Freivalds' Algorithm.

This will happen in room "Philippe Flajolet (2017)" next Monday (Sept 16) at 10:30 (30 minutes + discussion)


Freivalds' algorithm yields a surprisingly simple randomized O(n^2)-time solution for verifying whether an n x n matrix C is the product of two n x n matrices A and B. It is a long-standing open question whether this algorithm can be derandomized, i.e., whether matrix products can be verified deterministically in near-quadratic time. In this talk, we investigate a relaxation of this question: Can we derandomize Freivalds' algorithm using additional nondeterministic guesses?

We discuss consequences of a positive or negative answer to this relaxed question and provide potential avenues towards resolving it. Furthermore, we present the partial algorithmic progress that distinguishing whether an integer matrix product is correct or contains between 1 and n erroneous entries can be performed in time (n^2) -- interestingly, the difficult case of deterministic matrix product verification is not a problem of "finding a needle in the haystack", but rather cancellation effects in the presence of many errors.

Our main technical contribution is a deterministic algorithm that corrects an integer matrix product containing at most t errors in time ( n^2 + t^2). To obtain this result, we show how to compute an integer matrix product with at most t nonzeroes in the same running time.

Talk by Roman Kniazev: «Topos-theoretic point of view on directed spaces»

Speaker: Roman Kniazev
Location: Room Philippe Flajolet, LIX
Date: Mon, 15 Jul 2019, 15:00-16:00

For the next seminar of the Cosynus team, we are pleased to welcome Roman Kniazev, who will talk about Topos-theoretic point of view on directed spaces.

Abstract: Topos theory provides a very general framework for the investigation of connections between geometry and logic. For example, given a topological space X, category of sheaves on a category of open sets of X is a Grothendieck topos, whose internal logic can be applied for reasoning. We attempted to adapt the semantical counterpart for directed spaces: we considered a trace space as a base category for a sheaf topos and found some topos-theoretic invariants. Also, we studied the representation of time in a trace space and the additional structure it brings to the topos. Besides that, we will briefly discuss further research directions, such as types of the internal language and transition to a global description (like small/big topos). This is a report based on my internship in the team.