Laboratoire d'informatique de l'École polytechnique

News

Talk by Yoram Moses: «On Using Silence and Time in Distributed Protocols»

Speaker: Yoram Moses
Location: Room Grace Hopper
Date: Fri, 13 Dec 2019, 09:30-10:30

Yoram Moses from Technion will visit us next week, and will give a talk on Friday morning. The talk will be in room Grace Hopper, at 9:30 on December 13 and is entitled «On Using Silence and Time in Distributed Protocols».

Abstract: We consider how timing information can facilitate the design of efficient distributed protocols. In particular, we consider how it enables the use of silence - not sending messages - to obtain simple solutions with desirable properties. The talk will be self-contained, and will not assume any prior knowledge.

Short bio: Yoram Moses received a PhD from Stanford university in 1986, and is now a professor of electrical engineering and the Israel Pollack academic chair at the Technion. He received the Gödel award in 1997 and the Dijkstra prize in 2009, for his work on knowledge in distributed and multi-agent systems. Among other topics, he has recently been studying the use of time in computer networks, and has been applying distributed systems techniques to the study of asynchronous VLSI circuits.

Soutenance de thèse de Jérémy Ledent: «Sémantiques Géométriques pour la Calculabilité Asynchrone»

Speaker: Jérémy Ledent
Location: Amphi Sophie Germain, bât. Alan Turing
Date: Jeu. 12 déc. 2019, 15h00-17h00

Jérémie Ledent, doctorant dans l'équipe Cosynus, soutiendra sa thèse intitulée «Sémantiques Géométriques pour la Calculabilité Asynchrone» le Jeudi 12 décembre à 15h00, dans l'amphithéâtre Sophie Germain, bâtiment Alan Turing, sur le campus de l'École Polytechnique, à Palaiseau.

Mots clés : Protocoles tolérants aux pannes, Topologie, Logique épistémique

Résumé : Le domaine des protocoles tolérants aux pannes étudie quelles tâches concurrentes sont résolubles dans différents modèles de calcul avec pannes. Des outils mathématiques basés sur la topologie combinatoire ont été développés depuis les années 1990 pour aborder ces questions. Dans ce cadre, la tâche que l’on veut résoudre, et le protocole auquel on fait appel, sont modélisés par des complexes simpliciaux chromatiques. On définit qu’un protocole résout une tâche lorsqu’il existe une certaine application simpliciale entre ces complexes. Dans cette thèse, on étudie ces méthodes géométriques du point de vue de la sémantique. Le premier objectif est de fonder cette définition abstraite de résolution d’une tâche sur une autre plus concrète, basée sur des entrelacements de traces d’exécution. On examine diverses notions de spécifications pour les objets concurrents, afin de définir un cadre général pour la résolution de tâches par des objets partagés. On montre ensuite comment extraire de ce cadre la définition topologique de résolubilité de tâches. Dans la deuxième partie de la thèse, on prouve que les complexes simpliciaux chromatiques peuvent être utilisés pour évaluer des formules de logique épistémique. Cela permet d’interpréter les preuves topologiques d’impossibilité en fonction de la quantité de connaissances à acquérir pour résoudre une tâche. Enfin, on présente quelques liens préliminaires avec la sémantique dirigée pour les programmes concurrents. On montre comment la subdivision chromatique d’un simplexe peut être retrouvée en considérant des notions combinatoires de chemins dirigés.

Soutenance de thèse de Robin Larrieu: «Arithmétique rapide pour des corps finis»

Speaker: Robin Larrieu
Location: Amphi Sophie Germain, bât. Alan Turing
Date: Mar. 10 déc. 2019, 14h00-16h00

Robin Larrieu, de l'équipe MAX, soutiendra sa thèse intitulée Arithmétique rapide pour des corps finis le 10 décembre 2019 à 14h, en salle Gilles Kahn.

Mots clés : Corps finis, Algorithme, Arithmétique polynomiale, FFT, Bases de Gröbner

Résumé : La multiplication de polynômes est une opération fondamentale en théorie de la complexité. En effet, pour de nombreux problèmes d’arithmétique, la complexité des algorithmes s’exprime habituellement en fonction de la complexité de la multiplication. Un meilleur algorithme de multiplication permet ainsi d’effectuer les opérations concernées plus rapidement. Un résultat de 2016 a établi une meilleure complexité asymptotique pour la multiplication de polynômes dans des corps finis. Cet article constitue le point de départ de la thèse ; l’objectif est d’étudier les conséquences à la fois théoriques et pratiques de la nouvelle borne de complexité.

La première partie s’intéresse à la multiplication de polynômes à une variable. Cette partie présente deux nouveaux algorithmes censés accélérer le calcul en pratique (plutôt que d’un point de vue asymptotique). S’il est difficile dans le cas général d’observer l’amélioration prévue, certains cas précis sont particulièrement favorables. En l’occurrence, le second algorithme proposé, spécifique aux corps finis, conduit à une meilleure implémentation de la multiplication dans F_2 [X], environ deux fois plus rapide que les logiciels précédents.

La deuxième partie traite l’arithmétique des polynômes à plusieurs variables modulo un idéal, telle qu’utilisée par exemple pour la résolution de systèmes polynomiaux. Ce travail suppose une situation simplifiée, avec seulement deux variables et sous certaines hypothèses de régularité. Dans ce cas particulier, la deuxième partie de la thèse donne des algorithmes de complexité asymptotiquement optimale (à des facteurs logarithmiques près), par rapport à la taille des entrées/sorties. L’implémentation pour ce cas spécifique est alors nettement plus rapide que les logiciels généralistes, le gain étant de plus en plus marqué lorsque la taille de l’entrée augmente.

Exposé par Adeline Pierrot: «Formes limites de permutations à motifs interdits»

Speaker: Adeline Pierrot
Location: Salle Philippe Flajolet, bât. Alan Turing
Date: Wed, 4 Dec 2019, 10:30-11:30

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 10h30 dans la salle Philippe Flajolet du LIX. Adeline Pierrot (LRI, Université Paris Saclay) nous parlera de Formes limites de permutations à motifs interdits.

Résumé: On s'intéresse aux ensembles de permutations à motifs exclus, appelés classes de permutations, qui ont été beaucoup étudiés en combinatoire énumérative. Dans ce travail, à la frontière entre combinatoire et probabilités, on s'intéresse à la limite d'échelle d'une grande permutation aléatoire uniforme dans une classe de permutation. On décrit cette limite en terme de permuton, objet pouvant être vu comme une permutation de taille infinie. Un outil clé est la décomposition par substitution des permutations, qui permet de voir les permutations comme des arbres.

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

NOEMI: Assistant-e en gestion administrative

Le LIX propose un poste d'assistant(e) en gestion administrative dans le cadre de la campagne NOEMI du CNRS. Il ou elle sera chargé(e) de coordonner et de réaliser les activités de gestion administrative financière et de ressources humaines de plusieurs équipes de l'unité de manière autonome.

Pour en savoir plus, ou pour postuler, merci de vous référer à l'annonce sur le site NOEMI

talk by Karima Makhlouf and Sami Zhioua: «Intuitive Introduction to Fairness and Privacy in Machine Learning»

Speaker: Sami Zhioua and Karima Makhlouf
Location: Room Emmy Noether -- Alan Turing building
Date: Fri, 29 Nov 2019, 14:00-15:00

The next Comète seminar will take place on Friday, November 29th at 2pm in Salle Emmy Noether (LIX - Alan Turing building, École Polytechnique). Karima Makhlouf (Université du Quebec à Montréal (UQAM), Canada) and Sami Zhioua (Higher Colleges of Technology, Dubai) will talk about Intuitive Introduction to Fairness and Privacy in Machine Learning.

Abstract: Machine Learning (ML) algorithms have penetrated every aspect of our daily life. From movie recommendations to driving autonomous cars, ML outperforms humans in algorithmic decision-making as they can take into account orders of magnitude more factors than people can. The dark side, however, is that ML algorithms are often vulnerable to biases that render their decisions “unfair” towards certain individuals and minorities. As ML is increasingly used in high-impact/life-changing decision making such as job hiring, University admission, and predicting whether released people from jail will re-offend, fairness becomes critically important. In this presentation, we explore the problem of fairness and privacy in machine learning. In particular, we discuss the different and often conflicting definitions of fairness, the origins of bias, and the currently existing approaches to ensure fairness in ML algorithms. The presentation is intended to be an intuitive introduction to the field.

Exposé par Marie Théret: «Cardinal d'un ensemble de coupure minimal en percolation de premier passage»

Speaker: Marie Théret
Location: Salle Philippe Flajolet (LIX)
Date: Mer. 27 nov. 2019, 10h30-11h30

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 10h30 dans la salle Philippe Flajolet du LIX. Marie Théret (Université Paris Nanterre) nous parlera de Cardinal d'un ensemble de coupure minimal en percolation de premier passage

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

Résumé : On considère le modèle de percolation de premier passage sur Z^d en dimension d≥2 : on associe aux arêtes du graphe une famille de variables i.i.d. positives ou nulles. On interprète la variable aléatoire associée à une arête comme étant sa capacité, i.e., la quantité maximale d'eau ou d'information qui peut la traverser par seconde. Il en découle une définition naturelle de flux maximal à travers une région bornée du graphe entre un ensemble d'émetteurs et un ensemble de récepteurs. Ce flux maximal est égale à la capacité minimale d'un ensemble de coupure, c'est-à-dire un ensemble d'arêtes tel que si on le retire du graphe on disconnecte totalement les émetteurs des récepteurs. Dans cet exposé, on s'intéressera à une des caractéristiques de cet ensemble de coupure minimal : son cardinal. Il s'agit d'un travail en collaboration avec Barbara Dembin (LPSM, Université de Paris)

Talk by Ashish Dandekar: «Calibration of noise for a privacy-preserving mechanism»

Speaker: Ashish Dandekar
Location: Room Emmy Noether, Alan Turing building
Date: Fri, 22 Nov 2019, 14:00-15:00

The next Comète seminar will take place on Friday, November 22nd at 2pm in Salle Emmy Noether (LIX - Alan Turing building, École Polytechnique). Ashish Dandekar, ENS, will talk about Calibration of noise for a privacy-preserving mechanism.

Abstract: The calibration of noise for a privacy-preserving mechanism depends on the sensitivity of the query and the prescribed privacy level. A data steward must make the non-trivial choice of a privacy level that balances the requirements of users and the monetary constraints of the business entity. We study various sources of randomness that are involved in the design of a privacy-preserving mechanism, namely the explicit randomness induced by the noise distribution and the implicit randomness induced by the data-generation distribution. The study leads us to a probabilistic calibration of privacy-preserving mechanisms with quantifiable privacy guarantees. We instantiate it for the Laplace mechanism by providing analytical results. We propose a cost model that bridges the gap between the privacy level and the compensation budget estimated by a GDPR compliant business entity. We illustrate a realistic scenario wherein the use of fine-tuning of the Laplace mechanism avoids the overestimation of the compensation budget.

Exposé par Cesar Ceballos: «Permutahedral matchings, zonotopal tilings, and d-partitions!»

Speaker: Cesar Ceballos
Location: Salle Philippe Flajolet, LIX
Date: Mer. 20 nov. 2019, 10h30-11h30

Ce mercredi à 10h30 nous aurons le plaisir d'écouter Cesar Ceballos (Université de Vienne) nous parler de «Permutahedral matchings, zonotopal tilings, and d-partitions!».

Le résumé est disponible ci-dessous.

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

Résumé: In this talk I will present higher dimensional generalizations of the following three concepts:

  1. perfect matchings of a hexagonal tiling,
  2. rhombus tilings of a hexagon, and
  3. plane partitions.

I will show that these generalizations are equivalent under certain specific bijections. The generalizations of (b) and (c) have been already studied in the literature but, as far as I know, the generalization of (a) appears to be new. This is work in progress based on discussions with Tomack Gilmore and Vivien Ripoll.

Exposé par Luis Miguel Pardo: «Une preuve élémentaire de l'inégalité de Bézout de Heintz»

Speaker: Luis Miguel Pardo
Location: Salle Grace Hopper
Date: Mon, 18 Nov 2019, 14:00-16:00

Luis Miguel Pardo (Prof. Univ. Santander, Espagne), actuellement invité DER Polytechnique dans l'équipe MAX (oct.—nov.), donnera un exposé sous forme d'un mini-cours le lundi 18 novembre en salle Grace Hopper de 14h à 16h.

Résumé: À l'occasion de la rédaction d'un texte sur l'algorithme « Kronecker » accessible à une large audience, nous avons été amenés à écrire une preuve complète de l'inégalité de Bézout de Heintz pour les variétés algébriques avec des arguments mathématiques disons élémentaires. Dans le même temps nous fournissons une extension de cette inégalité pour les ensembles constructibles, ainsi que quelques applications nouvelles à certains problèmes algorithmiques. Cet exposé présentera les grandes lignes de ces preuves élémentaires. Les applications, vers la fin de l'exposé, seront liées à quelques idées nouvelles autour des ensembles questeurs ("correct test sequences") pour les systèmes d'équations polynomiales.

Exposé par Kaveh Mousavand: «Brauer-Thrall Conjectures, Old and New!»

Speaker: Kaveh Mousavand
Location: Salle Flajolet, LIX
Date: Wed, 13 Nov 2019, 10:30-11:30

Ce mercredi à 10h30 nous aurons le plaisir d'écouter Kaveh Mousavand (UQAM) nous parler de «Brauer-Thrall Conjectures, Old and New!».

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

À mercredi, Jérémie, Éric et Viviane.

Résumé: τ-tilting theory is an elegant -- but technical -- subject in representation theory of associative algebras, with motivations from cluster algebras. It was introduced by Adachi-Iyama-Reiten, in 2014. However, thanks to the recent result of Demonet-Iyama-Jasso, one can fully phrase the concept of τ-tilting finiteness in terms of linear algebra. I adopt this elementary approach to share some new results on τ-tilting finiteness of several families of algebras with rich combinatorics.

I begin with a review of two fundamental conjectures by Brauer and Thrall. After some historical remarks on those, I present a gentle introduction to τ-tilting finiteness, which allows me to state a conjecture of similar nature that relies on my recent work on τ-tilting theory. I will share my main strategy, as well as my new results on some cases.

I will not assume any prior knowledge of representation theory of algebras!

Exposé par Paul Thevenin: «Geometry of random permutation factorizations»

Speaker: Paul Thevenin (CMAP)
Location: Salle Philippe Flajolet, LIX
Date: Mer. 6 nov. 2019, 10h30-11h30

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 10h30 dans la salle Philippe Flajolet du LIX. Paul Thevenin (CMAP, École Polytechnique) nous parlera de Geometry of random permutation factorizations.

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

Résumé : We study random minimal factorizations of the n-cycle into transpositions, that is, factorizations of the cycle (12...n) into a product of n−1 transpositions. It is known that these factorizations are in bijection with Cayley trees of size n, and therefore that there are nn−2 of them. Moreover, they are naturally coded by sequences of sets of non-crossing chords in the unit disk. We establish the existence of a limit for such sets of chords, when they code a uniform random minimal factorization of the cycle. We show in particular how this random limit is naturally encoded in a Brownian excursion. The key tool of this study is an explicit bijection between minimal factorizations of the n-cycle and a family of trees with n labelled vertices. Finally, we explain how this framework can be extended to factorizations of (12...n) into cycles that are not necessarily transpositions, giving birth to new random structures.

Talk by G. Loukides: «String sanitization: a combinatorial approach»

Speaker: Grigorios Loukides
Location: Room Grace Hopper, LIX - Alan Turing building
Date: Thu, 31 Oct 2019, 14:00-15:00

The next Comète seminar will take place next Thursday October 31st at 14h in Salle Grace Hopper (LIX - Alan Turing building, École Polytechnique). Grigorios Loukides (Assistant Professor in the Department of Informatics, King's College London) will talk about "String sanitization: a combinatorial approach".

Abstract: String data are often disseminated to support applications such as location-based service provision or DNA sequence analysis. This dissemination, however, may expose sensitive patterns that model confidential knowledge (e.g., trips to mental health clinics from a string representing a user's location history). In this talk, I will examine the problem of sanitizing a string by concealing the occurrences of sensitive patterns, while maintaining data utility. First, I will present a time-optimal algorithm, TFS-ALGO, to construct the shortest string preserving the order of appearance and the frequency of all non-sensitive patterns. Such a string allows accurately performing tasks based on the sequential nature and pattern frequencies of the string. Second, I will present a time-optimal algorithm, PFS-ALGO, which preserves a partial order of appearance of non-sensitive patterns but produces a much shorter string that can be analyzed more efficiently. The strings produced by either of these algorithms may reveal the location of sensitive patterns. In response, I will present a heuristic, MCSR-ALGO, which replaces letters in these strings with carefully selected letters, so that sensitive patterns are not reinstated and occurrences of spurious patterns are prevented. Last, I will present experiments showing that our sanitization approach that applies TFS-ALGO, PFS-ALGO and then MCSR-ALGO is effective and efficient.

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 : https://galac.lri.fr/pages/combi-seminar.html

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).

Abstract:

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 (http://contentcheck.inria.fr/).

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 : https://galac.lri.fr/pages/combi-seminar.html

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)

Abstract:

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.

http://drops.dagstuhl.de/opus/volltexte/2018/9519/