Laboratoire d'informatique de l'École polytechnique

News

Séminaire par Véronique Bazier-Matte : «Conjecture d'unistructuralité des algèbres amassées»

Speaker: Véronique Bazier-Matte (LaCIM, UQAM)
Location: Salle Philippe Flajolet du LIX
Date: Mer. 18 avr. 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 Véronique Bazier-Matte (LaCIM, UQAM) nous parler de «Conjecture d'unistructuralité des algèbres amassées»

Resumé: En 2014, Assem, Schiffler et Shramchenko ont émis comme conjecture que toute algèbre amassée est unistructurelle, c'est-à-dire que l'ensemble des variables amassées détermine uniquement la structure d'algèbre amassée. Cette conjecture a été prouvée pour les algèbres de type fini, de rang 2 ou de type A-tilde. Dans cet exposé, nous exposerons quelques définitions et propriétés de base des algèbres amassées et nous expliquerons le concept d'unistructuralité des algèbres amassées. Puis, nous esquisserons la preuve pour certains cas où la conjecture est vérifiée. Pour ce faire, nous utiliserons les triangulations de surface et l'indépendance algébrique des amas.

Prochain séminaire BlockSem: Bruno Biais

Location: Salle Gilles Kahn, bâtiment Turin
Date: Jeu. 5 avr. 2018, 11h00-16h00

Pour la prochaine séance, il n’est prévu qu’un seul exposé: Bruno Biais nous parlera de «The blockchain folk theorem». En début d’après-midi, nous avons prévu une réunion informelle pour discuter d’orientations possibles/souhaitables pour BlockSem (e.g., nouveaux sujets, autres formes des interventions, fréquence, …).

Toutes les informations sont sur la page du séminaire.

Journées Nationales Informatique Mathématique

Location: École polytechnique, Palaiseau, France
Date: Mar. 3 avr. 2018, 14h00 - Ven. 6 avr. 2018, 16h00

Le LIX organise cette année sur le campus de l'X les Journées Nationales de l'Informatique Mathématique (JNIM'2018), événement phare du GdR Informatique Mathématique:

https://jnim2018.sciencesconf.org/

Nous aurons d'ailleurs le plaisir d'entendre, entre autres exposés donnés lors de ces journées, ceux de Marie-Paule Cani (Stream) et de Catuscia Palamidessi (Comète), ainsi que des anciens du LIX/DIX, Assia Mahboubi et Philippe Jacquet.

Nous vous attendons donc nombreux à cet événement, qui se conclura par une journée en hommage à Maurice Nivat.

La participation est gratuite, mais l'inscription est obligatoire : https://jnim2018.sciencesconf.org/registration

Inscrivez-vous !

Contacts: Stéphane Graham-Lengrand et Grégoire Lecerf

Exposé par Bérénice Delcroix-Oger: «Théorème de rigidité et fonctions de Parking»

Speaker: Bérénice Delcroix-Oger
Location: salle Philippe Flajolet, bât. Alan Turing
Date: Mer. 21 mars. 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 Bérénice Delcroix-Oger (IRIF) nous parler de «Théorème de rigidité et fonctions de Parking».

Résumé: Une question classique, mais difficile, de combinatoire algébrique est de savoir si une algèbre d'un type donné est libre sur l'ensemble de ses générateurs. Après avoir introduit tous les prérequis, j'expliquerai en quoi les théorèmes de rigidité pour les opérades, introduits en 2008 par Loday et récemment étendus, permettent d'apporter une réponse à ce genre de problème, notamment en ce qui concerne les algèbres des fonctions de Parking et des surjections. Ce travail a été fait en collaboration avec Emily Burgunder.

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 !

Sémin'Ouvert : « Algorithmes disons rapides pour factoriser les polynômes » par Grégoire Lecerf (LIX, équipe MAX)

Speaker: Grégoire Lecerf
Location: amphi. Germain (bât. Turing)
Date: Jeu. 15 mars. 2018, 14h30-15h30

Nous commencerons cet exposé par un aperçu des problèmes classiques de calculabilité et complexité liés à la factorisation des polynômes à une ou plusieurs variables. Nous expliquerons ensuite comment les différents sous-problèmes s'organisent habituellement selon les types de factorisation, les coefficients, et le nombre de variables. Enfin, nous montrerons comment fonctionnent quelques algorithmes récents.

Exposé de Frédéric Chyzak: «Chemins tandems et chemins de Łukasiewicz : bijections et variations»

Speaker: Frédéric Chyzak
Location: Salle Philippe Flajolet, Bât. Alan Turing
Date: Wed, 7 Mar 2018, 11:00-12:00

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 Frédéric Chyzak (INRIA-SpecFun) nous parler de «Chemins tandems et chemins de Łukasiewicz : bijections et variations»

Résumé: Les chemins du quart de plan sur les pas O, N, SE (« chemins tandems ») et celles sur les pas O, NO, N, E, SE, S (« chemins tandems symétrisés ») sont connus pour avoir des séries génératrices algébriques lorsqu'ils sont énumérées par la longueur. Pour les premiers, D. Gouyou-Beauchamps a donné en 1989 une bijection en termes de chemins de Motzkin et de tableaux de Young. Pour les seconds, M. Bousquet-Mélou et M. Mishna ont en 2010 donné un calcul algébrique explicite de la série génératrice, par moyennisation d'une équation fonctionnelle vérifiée par la série. Ces dernières auteures ont de plus fait la remarque que la duplication symétrique des pas pour les chemins tandems symétrisés semble être reflétée d'une manière encore inexpliquée par un facteur 2^n dans leur dénombrement ; elles ont demandé une explication bijective du phénomène. Cet exposé donne des bijections pour approcher ces questions.

Dans un premier temps, nous montrerons comment des travaux de S.-P. Eu et de ses collaborateurs peuvent être revisités pour donner une bijection algorithmique directe du résultat de Gouyou-Beauchamps. Cette bijection et son inverse s'appuient sur des traversées uniques et unidirectionnelles de mots, en ne considérant qu'une information locale, alors que la méthode d'origine d'Eu requiert plusieurs itérations sur les mots, en considérant simultanément plusieurs lettres distantes. Cette présentation plus explicite de la bijection permet de plus de suivre des paramètres de position finale.

Ensuite, nous montrerons comment étendre la bijection précédente dans deux directions. D'une part, en allant au-delà des chemins de Motzkin par l'utilisation de grands pas positifs, nous obtenons une bijection entre les chemins p-Łukasiewicz du demi-plan supérieur, utilisant les pas (1, i) pour -1 <= i <= p, et les chemins p-tandems du quart de plan, utilisant le pas SE = (1, -1) et les pas (-i, p-i) pour 0 <= i <= p. D'autre part, en interférant habilement deux copies de la bijection pour les chemins tandems, nous obtenons une bijection entre chemins tandems symétrisés et une variété bicolorée de chemins de Motzkin.

De manière remarquable, des résultats bijectifs similaires apparaissent dans un travail en cours de M. Bousquet-Mélou, É. Fusy et K. Raschel, où les auteurs utilisent une bijection récente due à R. Kenyon, J. Miller, S. Sheffield et D. Wilson, entre chemins tandems généraux et orientations bipolaires marquées de cartes. Nos bijections sont pourtant différentes de celles à base de cartes, sans que les liens potentiels n'aient a ce jour été étudiés.

(Exposé sur deux travaux en cours avec A. Bostan, A. Mahboubi et K. Yeats.)

Exposé de Olivia Caramello

Speaker: Olivia Caramello
Location: Salle Schutzenberger, LIX
Date: Mon, 5 Mar 2018, 14:00-16:00

Un groupe de travail s'est formé pour étudier les théories et les techniques (topos, topos classifiants, logique du premier ordre, catégories syntactiques,...) utilisées par O. Caramello et sa philosophie des ponts.

Le premier exposé (introductif) sera donné par Olivia Caramello elle-même le lundi 5 mars à 14h en salle Schutzenberger au Laboratoire d'Informatique de l'Ecole Polytechnique. Les horaires des autres exposés seront déterminé par les préférence du groupe formé lors du premier exposé (on vise un exposé par semaine qui aurait lieu en après midi).

Talk by Bradley Worley: «Variational Bayesian Compressed Sensing»

Speaker: Bradley Worley
Location: Room Philippe Flajolet
Date: Thu, 22 Feb 2018, 14:30-15:30

We are pleased to welcome Bradley WORLEY (Institut Pasteur) next Thursday 22/02, 14h30, at LIX (building Alan Turing, 1 Rue Honoré d'Estienne d'Orves, 91120 Palaiseau) room Philippe Flajolet.

Abstract: Sparse recovery is a cornerstone of nonuniform sampling (NUS) methods in nuclear magnetic resonance (NMR), magnetic resonance imaging (MRI), and other instrumental techniques. While most recovery algorithms can find globally optimal solutions by means of convex optimization, they generally do not provide error estimates, which are critically important in scientific applications. We introduce the variational method of constructing approximate Bayesian inference algorithms, and show recent results of its use in NUS NMR reconstruction. Connections with existing compressed sensing algorithms and current efforts towards improved performance will also be presented.

Exposé de Justine Falque: «Algèbre des orbites des groupes à profil polynomial, théorèmes de Cameron et de Macpherson»

Speaker: Justine Falque (LRI)
Location: Salle Philippe Flajolet
Date: Mer. 21 févr. 2018, 11h00-12h00

Résumé: Étant donné un groupe de permutation infini G, on définit la fonction qui à tout entier naturel n associe le nombre d'orbites de sous-ensembles de cardinal n, pour l'action induite de G sur les sous-ensembles d'éléments. Cameron a conjecturé que cette fonction de comptage (le profil de G) est un quasi-polynôme dans le cas où sa croissance est polynomiale. Une autre conjecture, plus forte, a été émise plus tard par un de ses étudiants, Macpherson. Elle concerne une certaine structure d'algèbre graduée sur les orbites de sous-ensembles, créée par Cameron, et suppose que si le profil de G est polynomial, alors son algèbre des orbites est de type fini. L'exposé présentera ces deux conjectures et leur contexte, ainsi que les idées de la preuve de la conjecture de Macpherson, fruit d'un travail commun de Nicolas Thiéry et Justine Falque (avec les conseils précieux de Peter Cameron lui-même).

Talk by Prakash Panangaden: «Quantitative Equational Logic»

Speaker: Prakash Panangaden
Location: Salle Philippe Flajolet, (LIX - Alan Turing building)
Date: Mon, 12 Feb 2018, 14:00-15:00

The next Comète seminar will take place on Monday 12th of February 2017 at 14h00 in Salle Philippe Flajolet (LIX - Alan Turing building, École Polytechnique). Prakash Panangaden, Professor at McGill University School of Computer Science, will talk about his joint work with Radu Mardare and Gordon Plotkin: Quantitative Equational Logic.

Abstract: Equational reasoning is a central part of mathematics. The traditional theory links the equational logic and monads on the category of sets. More precisely, one can define an algebraic theory by giving a set of operations and equations. One can then show that the collection of algebras defined by these equations form the algebras for a monad on the category of sets. One has classical theorems like the completeness and variety theorems of Birkhoff. We consider a modified notion of equation where the equality symbol is annotated with a real number so we can write s =_e t with the interpretation that the terms "s" and "t" are within "e" of each other. We develop the metatheory and obtain some analogues of the classical theorems. Furthermore, we show that this extended notion of equational definition yields algebras of monads on the category of metric spaces. What makes the theory interesting is the fact that well known metric spaces of probability distributions can be defined by such equations.

PhD defense of Sonia Marin

Speaker: Sonia Marin
Location: Amphi. Sophie Germain, Alan Turing building
Date: Tue, 30 Jan 2018, 15:00-16:30

Sonia Marin will defend her PhD thesis entitled « Modal proof theory through a focused telescope » on Tuesday, January 30th at 3pm in Amphithéâtre Sophie Germain (bâtiment Turing).

Abstract: In this thesis, we consider the proof theory of modal logic to illustrate two uses of the synthetic inference rules extracted from focused proof systems. From one side of the "telescope", focusing allows us to analyse the internal machinery of inference rules. We show first how to emulate Simpson's labelled sequent calculus for intuitionistic modal logic with Liang and Miller's focused sequent calculus for first-order logic, therefore extending the result of Miller and Volpe to the intuitionistic case. Then, we propose a similar encoding though for ordinary (unlabelled) sequent calculus via an intermediate focused framework based on Negri's labelled sequent calculus. From the other side of the "telescope", focusing allows us to observe more global behaviours in proofs. In particular, we give completeness proofs for two nested sequent calculi for both classical and intuitionistic modal logic, first for a focused version, and then for a system merely based on synthetic inference rules. These rules only retain the transitions between big steps of reasoning forgetting most of the focused rules, which renders the system presentation clear and elegant while also simplifying the cut-elimination and completeness proofs.

Journée sur l'intelligence artificielle au LIX

Location: Amphi. Germain
Date: Jeu. 18 janv. 2018, 09h55-16h00

9h55 — 10h00 : présentation de la journée

10h00 — 11h : exposés d'équipes et discussions

  • Yanlei Diao (équipe CEDAR du LIX & d'Inria Saclay)
  • Marie-Paule Cani (équipe Stream du LIX)
  • Bertrand Beaufils (équipe DataShape d'Inria Saclay)
  • Yann Ponty (équipe Amibio du LIX)

11h — 12h : Jean-Gabriel Ganascia (Sorbonne Université, LIP6)

2010 : l’Odyssée de l’intelligence artificielle.
Après avoir rappelé les définitions historiques de l’intelligence artificielle, puis avoir évoqué les réussites de ces dernières années, nous brosserons un tableau des différentes problématiques abordées par l’intelligence artificielle en prenant pour fil conducteur les cinq grandes classes de fonctions cognitives que l’on essaie de simuler, à savoir les fonctions perceptives, la mémoire, la représentation des connaissance et l’apprentissage, le raisonnement, les fonctions expressives et enfin les fonctions exécutives. Nous terminerons en évoquant à la fois les déclarations excessives des grands acteurs de l'internet sur l’intelligence artificielle et, surtout, le caractère « tressé » du temps technologique qui fait que des approches tombées en désuétudes reviennent souvent sur le devant de la scène.


13h50 — 14h10 : Bertrand Braunschweig (Inria Saclay)

14h10 — 16h00 : exposés d'équipes et discussions

  • Stéphane Graham-Lengrand (équipe Parsifal du LIX & d'Inria Saclay)
  • Benjamin Doerr (équipe AlCo du LIX)
  • Ulrich Fahrenberg (équipe Cosynus du LIX)
  • Michel Fliess (équipe MAX du LIX)
  • Catuscia Palamidessi (équipe Comete du LIX & d'Inria Saclay)
  • Jesse Read (équipe Dascim du LIX)

Talk by Adina Panchea: «Towards autonomous and bio-inspired control system design»

Speaker: Adina Panchea (Cosynus)
Location: Room Philippe Flajolet
Date: Tue, 16 Jan 2018, 14:00-15:00

Abstract: In this talk, I will present how I tackled, during my research projects, some of the activities encountered when designing a control system. Designing a control system implies a number of options, decisions and compromises which depend on the properties of the controlled system and on the required performances. To design a control system, the modelling, controller design, analysis, simulation, implementation and verification steps, which represent research directions by themselves, are often required.

I applied an alternative old approach of deriving optimal control laws such as inverse problems of variations calculus or inverse optimal control (IOC) which arouse a renewal of interest among researchers during the years. I addressed inverse optimal control and inverse optimization approaches based parametrized Lagrangians, which reduces the nonlinear parametric optimization problems to linear least square optimization, hence being easier to solve. I used IOC approach to analyse and propose simply but efficient bio-inspired models for redundant biological rhythmical motions, such as: arm motion, postural sway-and-balance, fast-and-normal human locomotion and squat movements. Moreover, I used this IOC approach as a tool to discriminate and reproduce the human fast-and-normal gait for patients with Parkinson’s disease (PD). By combining different research topics such as: estimation, least square methods and interval analysis, I propose a novel IOC method solved in a bounded-error framework was proposed.

Recently, I addressed the navigation planning level for the autonomous navigation of mobile robots and I proposed and validated on a easy to reproduce robotic platform, a new optimal (in terms of path length) and a robust motion planning algorithm based incremental sampling-based motion algorithm, i.e. Rapidly-exploring Random Tree (RRT) and its optimal versions based interval analysis tools.