Laboratoire d'informatique de l'École polytechnique

News

Talk by Sergio Mover: «Verifying Hybrid Systems with Logic-based Model Checking»

Speaker: Sergio Mover
Location: Room Gilles Kahn, Alan Turing building
Date: Tue, 16 Oct 2018, 10:30-11:30

For the next seminar, we will have the pleasure of welcoming Sergio Mover who has recently joined us in the Cosynus team.

Abstract: Hybrid systems can model complex systems that we have to trust (e.g., the landing gear subsystem of on an airplane) and where software interacts with the physical environment. In this seminar, I will mainly focus on an automatic formal verification technique for Hybrid Systems that is based on a reduction to discrete, but still infinite states, transition systems. I will first explain the first-order logic formalism used to represents discrete systems and verification algorithms based on Satisfiability Modulo Theories (SMT). I will then describe the reduction of (subclasses of) hybrid systems to discrete systems and show different applications of the approach. Then, I will briefly switch topic and introduce an ongoing research project, Fixr, where we tackle the problem of exploiting existing "program artifacts" (e.g., source code, execution traces) to build assistive technology (e.g., similar code search, bug finding, automatic bug repair). I will conclude discussing some future research directions.

Sabrina Ouazzani est lauréate d'une bourse L’Oréal-UNESCO

Sabrina Ouazzani, post-docdorante dans l'équipe AlCO depuis le 1er septembre, est lauréate d'une bourse l’Oréal-UNESCO Pour les Femmes et la Science.

Voir: l'annonce sur Twitter.

Félicitations à elle!

Séminaire par François Bergeron: «Comprendre la combinatoire des fonctions “parking" rectangulaire via les espaces de polynômes harmoniques diagonaux»

Speaker: François Bergeron
Location: Salle Philippe Flajolet, bât. Alan Turing
Date: Mer. 3 oct. 2018, 11h00-12h00

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 11h dans la salle Philippe Flajolet du LIX. Nous aurons le plaisir d'écouter François Bergeron (UQAM) nous donner son premier exposé sur «Comprendre la combinatoire des fonctions “parking" rectangulaire via les espaces de polynômes harmoniques diagonaux».

Résumé: Dans cette suite d’exposés, j’ai l’intention d’expliquer comment de nouveaux espaces de polynômes multivariés permettent: de rendre compte de la riche combinatoire des généralisations rectangulaires des fonctions parking, des chemins de (m,n)-Catalan, et des treillis de (m,n)-Tamari; de comprendre les familles de fonctions symétriques issues de l’étude des opérateurs de l’algèbre de Hall elliptique, et de mettre en évidence leurs symétries; d’unifier les divers énoncés des variantes de la conjecture Delta; de comprendre les symétries des super-polynômes des (m,n)-noeuds/entrelacs sur le tore; etc. Tout cela ouvre la porte à de nombreux nouveaux problèmes allant de la combinatoire énumérative, à la théorie de la représentation, en passant par la théorie des fonctions symétriques et la physique théorique (pour n’en citer que deux). Plusieurs nouvelles conjectures seront discutées en cours de route. Au besoin (selon les souhaits par l’auditoire) toutes les notions préliminaires nécessaires pourront être discutées. Pour la majorité des notions abordées, des outils de calcul formel sont disponibles ou en cours d'élaboration.

Séminaire par Thomas Seiller: «Dynamique, algèbre, géométrie, et complexité du calcul»

Speaker: Thomas Seiller
Location: Salle Philippe Flajolet, Bât. Alan Turing
Date: Ven. 28 sept. 2018, 10h30-11h30

Pour le prochain séminaire de notre équipe, nous aurons le plaisir d'accueillir Thomas Seiller.

Résumé: Le but de cet exposé est de présenter certains aspects géométriques des programmes et de la complexité algorithmique qui apparaissent lorsque l’on s’essaie à représenter la dynamique de l’execution des programmes. Le cadre formel que je considère, les modèles de graphes d’interaction, est inspiré des modèles de géométrie de l’interaction de Girard et permet de representer les programmes comme des généralisations de systèmes dynamiques. J’expliquerai comment cette approche me mène à étudier certaines relations d’équivalences entre actions de monoides, et comment ceci pourrait mener à de nouvelles techniques de séparation en complexité.

Exposé par Nicolas Ninin: «Topologie dans le Blue Brain Project»

Speaker: Nicolas Ninin
Location: Salle Marcel-Paul Schützenberger
Date: Fri, 21 Sep 2018, 14:00-15:00

Pour le prochain séminaire de l'équipe Cosynus, nous aurons le plaisir d'accueillir Nicolas Ninin qui nous parlera de topologie et de cerveau.

Résumé: Dans cette présentation, nous présenterons les (ou plutôt quelques) utilisations de la topologie que nous pratiquons au Blue Brain Project (BBP). Le BBP est un projet visant à construire un modèle numérique de cerveau de rat le plus précis possible . Depuis quelques années nous disposons d'une première version de ceci représentant d'une toute petite partie du néocortex (1 mm3). Il est possible de voir ce modèle comme un graphe dirigé et d'appliquer des méthodes de topologie algébrique classique pour tenter de l'analyser. Nous présenterons certains résultats obtenus (en 2015) dans une première partie, puis quelques analyses plus récentes sur des simulations de plasticité.

IFORS Distinguished Lectureship

At the beginning of August, Leo Liberti was awarded the IFORS Distinguished Lectureship (IDL). IFORS is the International Federation of Operations Research Societies, a sort of overarching OR society which pools all other OR societies in the world.

Talk by Prof. Prashant Shenoy: «Designing Systems and Applications for Transient Computing»

Speaker: Prof. Prashant Shenoy
Location: Room Grace Hopper, LIX
Date: Tue, 24 Jul 2018, 14:00-15:00

On Tuesday we will have a talk by a visiting scholar, Prof. Prashant Shenoy, from the University of Massachusetts Amherst. Please find below the information of the talk and a shot bio of Prashant.

Abstract: Traditional distributed systems are built under the assumption that system resources will be available for use by applications unless there is a failure. Transient computing is a new phenomena that challenges this assumption by allowing system resources to become unavailable at any time. Transiency arises in many domains such as cloud computing--in the form of revocable spot servers--and in data centers that rely on variable electricity prices or intermittent renewable sources of energy Transiency is inherently different from fault tolerance since resources do not fail, rather they become temporarily unavailable, and traditional fault tolerance mechanisms are not suitable for handling transient resource unavailability.

In this talk, I will discuss how systems and applications need to be rethought to run on transient computing systems. I will first describe a system called Yank that uses a new bounded-time virtual machine migration mechanism to handle transiency at a system level while being transparent to applications. I will then discuss how modern distributed applications can be made transiency-aware and present a Spark-variant called Flint that we have developed to exploit transient cloud computing. I will end with open research questions in this area and directions for future work.

About the speaker: Prashant Shenoy is currently a Professor and Associate Dean in the College of Information and Computer Sciences at the University of Massachusetts Amherst. He received the B.Tech degree in Computer Science and Engineering from the Indian Institute of Technology, Bombay and the M.S and Ph.D degrees in Computer Science from the University of Texas, Austin. His research interests lie in distributed systems and networking, with a recent emphasis on cloud and green computing. He has been the recipient of several best paper awards at leading conferences, including a Sigmetrics Test of Time Award. He serves on editorial boards of the several journals and has served as the program chair of over a dozen ACM and IEEE conferences. He is a fellow of the IEEE and the AAAS and a distinguished member of the ACM.

Talk by Emilio Carrizos: «Sparseness in Classification and Regression. New steps.»

Speaker: Emilio Carrizosa (University of Seville, Spain, and Copenhagen Business School, Denmark)
Location: Room Henri Poincaré
Date: Fri, 20 Jul 2018, 09:00-10:00

Abstract: Classification and regression problems may involve data sets with (many) more variables than those which can be easily understood and interpreted. Sparsity is then a need. In this talk we will review several challenging problems in classification and regression, as well as the solutions Mathematical Optimisation provides to obtain sparsity.

Talk by Ruth Misener: «Lexicographic Optimisation for Rescheduling»

Speaker: Ruth Misener (Imperial College, UK)
Location: Room Henri Poincaré
Date: Fri, 20 Jul 2018, 10:00-11:00

Abstract: Responding reactively in scheduling environments subject to uncertainty may be modeled using reoptimization. Reoptimization begins by optimally solving an initial problem instance which is subsequently perturbed. The new objective is to update the initial optimal solution into a good solution for the new instance. We propose greedy algorithms and prove that they are efficient and tight for a variety of perturbations. In the case of job rejection or processing time reduction, reoptimization starting from an arbitrary optimal solution is not effective. But if our initial solution is lexicographic optimal, then we achieve a much better ratio. This result implies that reoptimization should be considered a two-step process where the phase of initial optimization has its own significance. For the initial phase, we propose a novel, branch-and-bound lexicographic optimization approach using vectorial bounds. Computational experiments with respect to the standard, weighted method validate our algorithm. This work is joint with Dr Dimitris Letsios.

Distinguished Paper award in IJCAI 2018

Giannis Nikolentzos, Michalis Vazirgianis and their co-authors have received the Distinguished Paper award (7 awards among the 710 accepted papers) in the major international AI conference IJCAI 2018 for their paper A Degeneracy Framework for Graph Similarity.

Maks Ovsjanikov, lauréat de la médaille de bronze du CNRS

Maks Ovsjanikov, de l'équipe Stream, vient de se voir décerner la médaille de bronze du CNRS. Félicitations à lui !