Laboratoire d'informatique de l'École polytechnique

News

Amaury Pouly remporte le prix Ackermann 2017

Amaury Pouly est le lauréat 2017 du prix Ackermann (Ackermann Award).

Le prix Ackermann est le prix de l’EACSL (European Association for Computer Science Logic) qui récompense chaque année une thèse exceptionnelle dans les domaines de la Logique et la science Informatique. Le prix sera remis et présenté à la conférence annuelle de l’association (CSL’2017).

La thèse d’Amaury Pouly démontre en particulier que l’on peut caractériser le temps polynomial (la classe P de la question P=NP) comme les solutions de longueur polynomiale d’équations différentielles polynomiales. Ce résultat ouvre la voie à reformuler certaines questions et concepts de l’informatique théorique en termes d'équations différentielles ordinaires polynomiales. Il revisite par ailleurs les modèles de calcul analogiques et démontre que les ordinateurs analogiques et digitaux ont en réalité la même puissance de calcul, à la fois au niveau de ce qu’ils peuvent calculer (calculabilité) et de ce qu’ils peuvent résoudre en temps polynomial (complexité).

Amaury a effectué sa thèse en cotutelle entre le Laboratoire d’informatique de l’X (LIX), UMR Ecole Polytechnique et CNRS en France, et l’Université d’Algarve au Portugal. Ses directeurs de thèse sont Olivier Bournez, en France, et Daniel Graça, au Portugal.

Parution du livre Asymptotic Differential Algebra and Model Theory of Transseries

Nous avons le plaisir de vous annoncer la parution du livre Asymptotic Differential Algebra and Model Theory of Transseries dans la série Annals of Mathematics Studies co-écrit par Matthias Aschenbrenner, Lou van den Dries et Joris van der Hoeven. Voir http://press.princeton.edu/titles/11044.html.

Invitation au Congrès International des Mathématiciens 2018

Joris Van der Hoeven, avec ses coauteurs Matthias Aschenbrenner (UCLA) et Lou van den Dries (UIUC), a été invité pour le prochain congrès international des mathématiciens (ICM 2018) à Rio de Janeiro. Ils exposeront entre autres les résultats récents de leur livre sur l'algèbre différentielle asymptotique et la théorie des modèles des transséries.

Soutenance de thèse d'Alice Héliou

Speaker: Alice Héliou (Amib)
Location: Salle Sophie Germain, bâtiment Alan Turing
Date: Lun. 10 juill. 2017, 14h30-16h00

Alice Héliou (équipe Amib) soutiendra sa thèse intitulée Analyse des séquences génomiques : Identification des ARNs circulaires et calcul de l'information négative, le lundi 10 juillet à 14h30 en salle Sophie Germain du bâtiment Alan Turing.

Résumé : Le développement des techniques de séquençage à haut débit a permis de nombreuses avancées dans les domaines de la biologie et de la santé. Les données sont produites en grande quantité à des coûts toujours plus faibles, cependant leur stockage et leurs analyses demeurent de vastes sujets de recherche.

Dans un premier temps nous avons étudié l'identification des ARNs circulaires à partir des données de séquençage. L'alignement de ces données, appelées des lectures, pour identifier les ARNs circulaires est particulier. En effet, avant d'être séquencés les ARNs sont fragmentés aléatoirement en morceaux de taille environ 100. Ceux-ci sont ensuite lus lors du séquençage, on obtient ainsi les lectures. La jonction d'un ARN circulaire peut se retrouver à des positions aléatoires sur les lectures. Celles-ci s'alignent donc seulement partiellement à deux endroits sur le génome, au lieu d'avoir un match global. Nous avons proposé une nouvelle méthode permettant d'identifier les ARNs circulaires chez les Archées et les Bactéries. Nos résultats ont permis de montrer l'implication de la ligase de la famille Rnl3 dans la circularisation des ARNs chez l'archée Pyroccoccus Abyssi.

Dans un second temps, nous avons abordé de façon plus théorique l'analyse des séquences génomiques. L'analyse de ces séquences repose généralement sur leur alignement ou sur la distribution des mots présents. Nous nous sommes intéressés à une approche duale de celles-ci, en nous concentrant sur ce qui est absent, l'information négative. Plus précisément nous avons élaboré des algorithmes pour calculer les mots qui sont absents d'une séquence mais dont tous les facteurs sont présents, les mots absents minimaux. Nos algorithmes ont tous des complexités linéaires en temps et en espace, mais ils diffèrent sur le compromis entre temps de calcul et quantité de mémoire interne utilisée.

Soutenance de thèse de Thibault Manneville

Speaker: Thibault Manneville
Location: Amphi Sophie Germain, bâtiment Alan Turing
Date: Jeu. 6 juill. 2017, 14h00-15h30

Thibault Manneville soutiendra sa thèse intitulée Généralisations géométriques et combinatoires de l'associaèdre le jeudi 6 juillet 2017 à 14h dans l'amphithéâtre Sophie Germain du LIX (bâtiment Alan Turing).

Résumé: L'associaèdre se situe à l'interface de plusieurs domaines mathématiques. Combinatoirement, il s'agit du complexe simplicial des dissections d'un polygone convexe (ensembles de diagonales ne se croisant pas deux à deux). Géométriquement, il s'agit d'un polytope dont les sommets et les arêtes encodent le graphe dual du complexe des dissections. Enfin l'associaèdre décrit la structure combinatoire qui définit la présentation par générateurs et relations de certaines algèbres, dites « amassées ». Du fait de son omniprésence, de nouvelles familles généralisant cet objet sont régulièrement découvertes. Cependant elles n'ont souvent que de faibles interactions. Leurs études respectives présentent de notre point de vue deux enjeux majeurs : chercher à les relier en se basant sur les propriétés connues de l'associaèdre ; et chercher pour chacune des cadres combinatoire, géométrique et algébrique dans le même esprit. Dans cette thèse, nous traitons le lien entre combinatoire et géométrie pour certaines de ces généralisations : les associaèdres de graphes, les complexes de sous-mots et les complexes d'accordéons. Nous suivons un fil rouge consistant à adapter, à ces trois familles, une méthode de construction des associaèdres comme éventails (ensembles de cônes polyédraux), dite méthode des d-vecteurs et issue de la théorie des algèbres amassées. De manière plus large, notre problématique principale consiste à réaliser, c'est-à-dire plonger géométriquement dans un espace vectoriel, des complexes abstraits. Nous obtenons trois familles de nouvelles réalisations, ainsi qu'une quatrième encore conjecturale dont les premières instances constituent déjà des avancées significatives. Enfin, en sus des résultats géométriques, nous démontrons des propriétés combinatoires spécifiques à chaque complexe simplicial abordé.

Talk by Jean-Éric Pin: «Dual space of a lattice as the completion of a Pervin space»

Speaker: Jean-Éric Pin (Irif)
Location: Room Grace Hopper, Alan Turing Building
Date: Fri, 30 Jun 2017, 11:00-12:00

Abstract: In this survey lecture, I will mainly cover well-known results from a new angle. A Pervin space is simply a set equipped with a lattice of subsets. This notion suffices to define a natural notion of completion which appears to be the dual of the original lattice. One can then show that any lattice of subsets can be described by a set of inequations of the form u <= v, where u and v are elements of its dual space. Applications to formal languages and complexity classes will be given.

Soutenance de thèse d'Olivier Wang

Speaker: Olivier Wang
Location: Salle Gilles Kahn, bâtiment Alan Turing
Date: Wed, 28 Jun 2017, 14:00-15:30

Olivier Wang soutiendra sa thèse intitulée Analytics Learning for Rule-Based Systems le vendredi 28 juin 2017 à 14h00 dans la salle Gilles Kahn du bâtiment Alan Turing

Résumé: Les Règles Métiers (Business Rules en anglais, ou BRs) sont un outil communément utilisé dans l’industrie pour automatiser des prises de décisions répétitives. Le problème de l’adaptation de bases de règles existantes à un environnement en constante évolution est celui qui motive cette thèse. Des techniques existantes d’Apprentissage Automatique Supervisé peuvent être utilisées lorsque cette adaptation se fait en toute connaissance de la décision correcte à prendre en toute circonstance. En revanche, il n’existe actuellement aucun algorithme, qu’il soit théorique ou pratique, qui puisse résoudre ce problème lorsque l’information connue est de nature statistique, comme c’est le cas pour une banque qui souhaite contrôler la proportion de demandes de prêt que son service de décision automatique fait passer à des experts humains. Nous étudions spécifiquement le problème d’apprentissage qui a pour objectif d’ajuster les BRs de façon à ce que les décisions prises aient une valeur moyenne donnée.

Séminaire blockchain le 22 juin : deux exposés, Romaric Ludinard et Julien Prat

Location: Salle Gilles Kahn, bâtiment Alan Turing
Date: Jeu. 22 juin. 2017, 11h00-15h00

La prochaine séance du séminaire blocksem à l'École polytechnique se tiendra le 22 juin, salle Gilles Kahn (rdc bâtiment Turing, INRIA). Le programme complet et les résumés des exposés sont sur le site du séminaire.

11:00-12:00 Romaric Ludinard, ENSAI / CREST. Accord en système distribué.

12:00-13:30 Repas dans le hall du bâtiment.

13:30-15:00 (format mini cours) Julien Prat, CNRS, CREST. A Model of the Bitcoin Miners Market avec Walter Benjamin.

Talk by Jon Lee: «A geometric view of some relaxations in non-convex optimization»

Speaker: Jon Lee (U. Michigan)
Location: Room Gilles Kahn, Alan Turing building
Date: Fri, 16 Jun 2017, 14:00-15:00

Jon Lee (U. Michigan) will give a seminar on A geometric view of some relaxations in non-convex optimization. Mr Lee is visiting LIX for two months, until the end of July.

Abstract: Convex relaxation is at the heart of general-purpose methods for dealing with non-convexities in optimization. Non-convexities take many forms: integrality and low-dimensional non-convex functions are often encountered in mathematical-optimization model. We will look at some typical relaxations and seek to understand the fundamental trade off of tightness vs heaviness via a geometric approach. In particular, we will look in detail at: (i) facility-location problems, (ii) graph problems (e.g., packing, boolean-quadric/cut problems), and (iii) triple-products.

Sémin'Ouvert : « RNA Bioinformatics and ensemble dynamic programming » par Yann Ponty

Speaker: Yann Ponty
Location: Bât. Turing, amphi. Germain
Date: Jeu. 15 juin. 2017, 14h30-15h30

RiboNucleic Acids (RNAs) are fascinating biomolecules which, similarly to DNA, can be encoded as sequences over a four-letter alphabet, and perform a wide array of biological functions. However, unlike DNA, the precise function of a given RNA depends critically on its structure, adopted as the outcome of a folding process. Luckily, this intricate three-dimensional conformation can be adequately abstracted as a (non-crossing) list of contacts, i.e. a discrete combinatorial object. In this talk, I will emphasize how, over the past three decades, RNA biology has benefited from a continuous and fruitful cross-talk between discrete mathematicians, computer scientists and biochemists. At the center of this conversation lies the concept of dynamic-programming, an algorithmic design technique which solves a combinatorial optimization problem efficiently by taking advantage of a well-chosen decomposition of its search space. Extensions and optimized instances of this technique now allow to address, at a genomic scale, multiple questions related to the analysis of the Boltzmann ensemble and the sequence-structure(-function) relationship. These developments also raise well-defined open questions, motivating further studies of the underlying discrete structures.

2016 Journal of Complexity best paper award

Joris van der Hoeven and Grégoire Lecerf are co-winners of the 2016 Journal of Complexity best paper award for their article Even faster integer multiplication co-authored with David Harvey, and published in October 2016, Vol. 36, pp. 1-30.

HDR defense by Maks Ovsjanikov: «A Functional View of Geometry Processing»

Speaker: Maks Ovsjanikov
Location: Télécom ParisTech, 46 rue Barrault, Paris, amphi Estaunié
Date: Fri, 19 May 2017, 14:15-15:15

Maks Ovsjanikov will defend his habilitation thesis next week on May, 19th. It will take place at Télécom ParisTech, 46 rue Barrault, Paris, amphi Estaunié.

Abstract: The work presented in my habilitation dissertation describes a set of approaches for analyzing and processing 3D shapes and their relations. The main unifying theme of this work is the observation that many concepts in geometric data analysis can be considered, both in theory and in practice, as linear operators acting on real-valued functions defined on the shapes. Although this point of view has been common in some areas of mathematics, such as dynamical systems, representation theory or parts of differential geometry, it has only recently been adopted in digital geometry processing, where it has led to novel insights and efficient algorithms for a wide variety of problems including shape matching, tangent vector field analysis and shape comparison to name a few. I will give an overview of these and related techniques and demonstrate, in particular, how the functional operator point of view can be helpful in a variety of practical settings, both by providing a common language in which many operations can be expressed and by enabling the use of classical linear-algebraic tools in novel, and sometimes unexpected scenarios.

Sémin'Ouvert : « Combinatorics and applications of Schnyder woods » par Éric Fusy

Speaker: Éric Fusy
Location: Bât. Turing, amphi. Germain
Date: Thu, 18 May 2017, 14:30-15:30

Schnyder woods are combinatorial structures on planar triangulations (maximal planar graphs embedded on the sphere) that can be formulated as a certain partition of the edges into 3 spanning trees. These structures have found many algorithmic applications, for instance in graph drawing, succinct encoding of meshes, efficient routing in planar networks, etc. I will present some of these applications, with an emphasis on the interplay with combinatorics.

Talk by G. Cherubin: «Bayes, not Naïve: Security Bounds on Website Fingerprinting Defenses»

Speaker: Giovanni Cherubin
Location: Room Grace Hopper, Alan Turing building
Date: Wed, 17 May 2017, 14:00-15:00

The next Comète seminar will take place next Wednesday 17th of May 2017 at 14h00 in Salle Grace Hooper (LIX - Alan Turing building, École Polytechnique). Giovanni Cherubin, PhD candidate in Information Security with the CDT in Cyber Security at Royal Holloway University of London (RHUL), will talk about "'Bayes, not Naïve': Security Bounds on Website Fingerprinting Defenses" (abstract below).

Abstract: Website Fingerprinting attacks allow an adversary to predict which web pages a victim visits, even when she browses through Tor/VPN, by using Machine Learning classification techniques on the encrypted traffic she produces. To date, the common method for evaluating Website Fingerprinting defences is testing them against state-of-the-art attacks. This generated a 15 years-long arms race.

This talk presents a practical method for deriving security bounds for Website Fingerprinting defences, which is based on results of the Machine Learning theory (specifically, on the optimality of the Bayes classifier). The method gives, with respect to the set of features used by an adversary, a lower bound estimate of what the adversary can achieve, for any classifier he may use. This result: i) allows practitioners to evaluate and compare defences in terms of their security, and ii) it favours a shift of WF research to a classifier-agnostic identification of optimal features. The talk will then consider open questions, and future applications of the method.

GT Combi du Plateau de Saclay - Séance participative

Location: Salle Philippe Flajolet, bât. Alan Turing
Date: Mer. 3 mai. 2017, 11h00-12h00

Le prochain GT Combi du Plateau de Saclay aura lieu ce mercredi 3 mai à 11h dans la salle Philippe Flajolet du LIX. Il s'agira d'une séance participative, où chacun pourra présenter ses questions, conjectures, ou travaux en cours en lien avec la combinatoire. Le programme du GT Combi du Plateau de Saclay est disponible ici

Talk by Nelson Maculan: «Combinatorial optimization models with a polynomial number of variables and constraints for some problems in graphs»

Speaker: Nelson Maculan (Federal University of Rio de Janeiro)
Location: Room P. Flajolet, Alan Turing Building
Date: Tue, 25 Apr 2017, 15:00-16:00

Abstract: We present integer linear models with a polynomial number of variables and constraints for combinatorial optimization problems in graphs: optimum elementary cycles (whose traveling salesman problem), optimum elementary paths even in a graph with negative cycles, and optimum trees (whose Steiner tree problem) problems. Mots clefs : modeling combinatorial optimization problems, optimization in graphs, characterization of connected subgraphs.

Sémin'Ouvert : « Invariants géométriques de structures algébriques » par Samuel Mimram

Speaker: Samuel Mimram
Location: Bât. Turing, amphi. Germain
Date: Jeu. 20 avr. 2017, 14h30-15h30

Les systèmes de réécriture de mots fournissent, lorsqu'ils sont convergents, une façon agréable et efficace pour décider de l'égalité dans des monoïdes (ou dans des groupes). On peut se demander si cette méthode est universelle, c'est-à-dire si tout monoïde admet une présentation convergente finie. Une réponse négative a été apportée dans les années 80 par Squier, qui a élaboré une preuve utilisant des invariants "géométriques" des monoïdes (leurs groupes d'homologie), montrant ainsi l'intérêt de prendre en compte la "géométrie des calculs". Je présenterai ce résultats et, si le temps le permet, des extensions récentes à des problèmes d'algèbre universelle. Aucune connaissance préalable dans les domaines sus-mentionnés n'est bien sûr requise.

Talk by Adrien Le Coënt: «Control synthesis of nonlinear sampled switched systems using Euler's method»

Speaker: Adrien Le Coënt
Location: Room Philippe Flajolet, Alan Turing building
Date: Fri, 14 Apr 2017, 14:00-15:00

Abstract: We propose a symbolic control synthesis method for nonlinear sampled switched systems whose vector fields are one-sided Lipschitz. The main idea is to use an approximate model obtained from the forward Euler method to build a guaranteed control. The benefit of this method is that the error introduced by symbolic modeling is bounded by choosing suitable time and space discretizations. The method is implemented in the interpreted language Octave. Several examples of the literature are performed and the results are compared with results obtained with a previous method based on the Runge-Kutta integration method.