Laboratoire d'informatique de l'École polytechnique

News

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.

Talk by Reza Shokri: «Trusting Machine Learning: Privacy, Robustness, and Interpretability Challenges»

Speaker: Reza Shokri
Location: Room Grace Hopper, Alan Turing building
Date: Mon, 1 Jul 2019, 14:00-15:00

The next COMETE seminar will take place on Monday, 1 July 2019 at 2 PM in Salle Grace Hopper (LIX - Alan Turing building, École Polytechnique). Reza Shokri, Assistant Professor of Computer Science at the National University of Singapore (NUS), will talk about "Trusting Machine Learning: Privacy, Robustness, and Interpretability Challenges".

Abstract: Machine learning algorithms have shown an unprecedented predictive power for many complex learning tasks. As they are increasingly being deployed in large scale critical applications for processing various types of data, new questions related to their trustworthiness would arise. Can machine learning algorithms be trusted to have access to individuals' sensitive data? Can they be robust against noisy or adversarially perturbed data? Can we reliably interpret their learning process, and explain their predictions? In this talk, I will go over the challenges of building trustworthy machine learning algorithms in centralized and distributed (federated) settings, and will discuss the inter-relation between privacy, robustness, and interpretability.

Bio: Reza Shokri is an Assistant Professor of Computer Science at the National University of Singapore (NUS), where he holds the NUS Presidential Young Professorship. His research is on adversarial and privacy-preserving computation, notably for machine learning algorithms. He is an active member of the security and privacy community, and has served as a PC member of IEEE S&P, ACM CCS, Usenix Security, NDSS, and PETS. He received the Caspar Bowden Award for Outstanding Research in Privacy Enhancing Technologies in 2018, for his work on analyzing the privacy risks of machine learning models, and was a runner-up in 2012, for his work on quantifying location privacy. He obtained his PhD from EPFL. More information: https://www.comp.nus.edu.sg/~reza

Exposé par Éric Goubault: «Directed topological complexity»

Speaker: Éric Goubault
Location: Salle Philippe Flajolet, LIX
Date: Mon, 1 Jul 2019, 11:00-12:00

Pour le prochain séminaire de l'équipe Cosynus, nous aurons le plaisir d'accueillir Éric Goubault qui nous parlera de complexité topologique dirigée.

Résumé: I will introduce in this talk a variant of topological complexity, that can be applied to help classify directed spaces, and has applications to the study of dynamical systems in the large, such as differential inclusions. Directed topological complexity looks for specific partitions {F1,…,Fn,…} of the set of reachable states of some directed space X, such that there is a continuous section from each of the Fi to the space of directed paths which is right inverse to the end points map. The size of this partition measures the minimal complexity that a motion planning algorithm should have, for controlling such a system. Also, as in the classical case, this sheds an interesting light on a number of directed invariants, and we discuss in particular dicontractibility. We will also show some examples of calculations on directed graphs, a number of higher-dimensional spaces and in particular, directed spheres. This is ongoing work with Aurélien Sagnier and Michael Farber.

Exposé par Indranil Saha: «Developing Autonomous Multi-Robot Systems for Complex Missions»

Speaker: Indranil Saha
Location: Salle Philippe Flajolet, LIX
Date: Mar. 25 juin. 2019, 10h00-11h00

Pour le prochain séminaire de l'équipe Cosynus, nous aurons le plaisir d'accueillir Indranil Saha, qui nous parlera de Developing Autonomous Multi-Robot Systems for Complex Missions.

Résumé: Autonomous multi-robot systems have tremendous potential to be useful in various applications, including search and rescue, surveillance, law enforcement, precision agriculture, and warehouse management. Given a high-level mission specification for a multi-robot system, it is technically challenging to determine the responsibilities of the individual robots and a plan for them to execute their tasks safely in such a way that the mission becomes successful. In this talk, I will present a framework for developing multi-robot systems where the mission specification is provided using a set of linear temporal logic (LTL) properties, and the dynamics of the robots are captured in the form of a set of motion primitives. We formulate the planning problem as an SMT solving problem and use an off-the-shelf SMT solver to generate safe trajectories for the robots. I will discuss various challenges that we face in scaling up our solution to large-scale multi-robot systems and describe how we address some of those challenges. As an extension, I will present how the multi-robot coverage problem can be effectively solved in our framework.

Le séminaire suivant aura lieu le lundi 01 juillet 2019 à 11h00 par Éric Goubault : Directed topological complexity.

La liste des prochains séminaires se trouve ici : http://www.lix.polytechnique.fr/cosynus/seminar/

Le calendrier des séminaires : http://www.lix.polytechnique.fr/cosynus/seminar/calendar.ics

Soutenance de thèse d'Alina Mayorova: «Liens combinatoires entre fonctions quasisymétriques et tableaux dans les groupes de Coxeter»

Speaker: Alina Mayorova
Location: Amphi. Sophie Germain, LIX
Date: Mer. 12 juin. 2019, 15h00-17h00

Alina Mayorova, de l'équipe Combi, soutiendra sa thèse intitulée «Liens combinatoires entre fonctions quasisymétriques et tableaux dans les groupes de Coxeter», le mercredi 12 juin 2019 à 15h dans l'amphithéâtre Sophie Germain du bâtiment Alan Turing.

Résumé: L’algèbre des fonctions symétriques est un outil majeur de la combinatoire algébrique qui joue un rôle central dans la théorie des représentations du groupe symétrique. Cette thèse traite des fonctions quasisymétriques, une puissante généralisation introduite par Gessel en 1984, avec des applications significatives dans l’énumération d’objets combinatoires majeurs tels que les permutations, les tableaux de Young et les P-partitions et dans l’étude de fonctions symétriques avancées telles que les polynômes de Schubert et Macdonald. Plus précisément, nous trouvons un nouveau lien entre l’extension des fonctions quasisymétriques de Chow à des groupes de Coxeter de type B et des tableaux de dominos, c’est-à-dire des diagrammes de Young pavés par des rectangles 2 × 1 et 1 × 2. Ceci nous permet d’apporter de nouveaux résultats dans divers domaines, notamment les constantes de structure de l’algèbre de descente de Solomon de type B, l’extension de la théorie de la Schur-positivité aux permutations signées et l’étude d’une formule de Cauchy de type B q-déformée avec des implications importantes statistiques pour les tableaux dominos.

Exposé par Nathan Williams: «Independence posets»

Speaker: Nathan Williams
Location: Salle Philippe Flajolet, LIX
Date: Mer. 12 juin. 2019, 11h00-12h00

Pour la dernière séance de l'année, le séminaire Combi du Plateau de Saclay accueille Nathan Williams de l'université de Dallas. Il nous parlera de "Independence Posets". Le résumé est disponible ci-dessous. Le séminaire aura lieu à 11h en salle Philippe Flajolet au LIX. Par ailleurs, à 15h, Alina Mayorova soutient sa thèse dans l'amphithéâtre Sophie Germain.

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

Résumé: Let G be an acylic directed graph. For each vertex of G, we define an involution on the independent sets of G. We call these involutions flips, and use them to define a new partial order on independent sets of G.

Trim lattices generalize distributive lattices by removing the graded hypothesis: a graded trim lattice is a distributive lattice, and every distributive lattice is trim. Our independence posets are a further generalization of distributive lattices, eliminating also the lattice requirement: an independence poset that is a lattice is always a trim lattice, and every trim lattice is the independence poset for a unique (up to isomorphism) acyclic directed graph G. This is joint work with Hugh Thomas.

Catuscia Palamidessi obtient une bourse ERC Advanced Grant

Catuscia Palamidessi, responsable de l'équipe Comete, est lauréate d'une bourse du Conseil Européen de la Recherche (ERC) pour son projet HYPATIA - Privacy and Utility Allied. L'objectif de projet est d'optimiser la sécurisation et l’utilité des données numériques personnelles.

Pour plus d'information, voir l'annonce sur le site d'Inria.

Exposé par Baptiste Louf: «Hiérarchies KP/2-Toda et cartes biparties»

Speaker: Baptiste Louf
Location: Salle Philippe Flajolet, LIX
Date: Mer. 29 mai. 2019, 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 Baptiste Louf (IRIF, Univ. Paris 7) nous donner un exposé sur «Hiérarchies KP/2-Toda et cartes biparties». 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é: Les hiérarchies intégrables (des ensembles infinis d’EDPs en une infinité de variables) sont étudiées depuis longtemps en physique mathématique. De manière assez surprenante, la série génératrice des cartes est une solution des hiérarchies KP et 2-Toda (qui est une généralisation de la précédente), ce qui permet d’obtenir des formules de récurrences exactes et très simples sur les coefficients (Goulden—Jackson, Carrell—Chapuy, Kazarian—Zograf). Je décrirai un peu la théorie derrière la hiérarchie 2-Toda et la preuve que la série des cartes en est solution (qui implique entre autres, des fonctions symétriques), et je dériverai une formule permettant de compter les cartes biparties à degrés des faces prescrits.

Exposé par Cécile Mammez: «Mots tassés stricts croissants, fonctions quasi-symétriques et fonctions symétriques non commutatives; éléments primitifs»

Speaker: Cécile Mammez
Location: Salle Philippe Flajolet
Date: Mer. 22 mai. 2019, 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 Cécile Mammez (Univ. de Nice) nous donner un exposé sur «Mots tassés stricts croissants, fonctions quasi-symétriques et fonctions symétriques non commutatives; éléments primitifs». 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é: Une algèbre de Hopf est un espace vectoriel muni d’une structure de bigèbre (ie d’une structure d’algèbre et de cogèbre avec une relation de compatibilité) et d’un antimorphisme d’algèbres particulier appelé antipode. L’objectif de cet exposé est d’expliquer les connections entre les mots tassés stricts croissants d’une part et les algèbres de Hopf des fonctions quasi-symétriques QSym et des fonctions symétriques non commutatives NSym d’autre part ainsi que d’en déduire des éléments primitifs de NSym. Pour cela, nous commencerons par rappeler la notion d’algèbre de Hopf ainsi que les définitions de QSym et NSym.

Nous expliquerons ensuite la construction des mots tassés stricts croissants et expliciterons sa structure d’algèbre de Hopf. Nous décrirons une familles d’éléments primitifs. Nous montrerons que son dual gradué est isomorphe à l’algèbre de Hopf des fonctions quasi-symétriques. Ainsi, l’algèbre de Hopf des mots tassés stricts croissants est

isomorphe à celle des fonctions symétriques non commutatives. La dernière partie de l’exposé sera consacrée à l’explicitation d’un isomorphisme explicite entre les mots tassés stricts croissants et NSym pour en déduire des éléments primitifs de cette dernière.

Jérémy Dubut -- Categorical approaches to bisimilarity

Speaker: Jérémy Dubut
Location: Salle Philippe Flajolet, LIX
Date: Jeu. 16 mai. 2019, 14h00-15h00

Pour le prochain séminaire de l'équipe Cosynus, nous aurons le plaisir d'accueillir Jérémy Dubut qui nous parlera d'approches catégoriques pour la bisimilarité.

Résumé: There are different categorical approaches to variations of transition systems and their bisimulations. One is coalgebras, another one is open maps. In this talk, I will describe these two approaches, illustrated by the case of labelled transition systems (almost no knowledge in category theory is needed for this part). I will then describe how it is possible to translate one into the other in some cases. From open maps to coalgebras, this was done by Lasota, using multi-sorted transition systems. From coalgebras to open maps, this was done in my joint work with Thorsten Wißmann, Shin-ya Katsumata and Ichiro Hasuo, where we derived path-categories and trace semantics for free for different flavors of categories of coalgebras with non-deterministic branching. I will illustrate those constructions on various concrete examples (tree automata, regular nominal automata, ...).

Sémin'Ouvert : « From the discrete world to the continuous world », par Jérémie Bettinelli (équipe Combi)

Speaker: Jérémie Bettinelli
Location: amphi. Germain (bât. Turing)
Date: Thu, 16 May 2019, 14:30-15:30

During this talk, I will present several accessible combinatorial structures known to converge toward interesting continuous limiting objects. Typically, if we possess, for a fixed integer n a finite number of combinatorial objects of "size" n, one may choose one uniformly at random and obtain a random combinatorial object. It often happens that, after scaling if necessary, this random discrete object converges toward a continuous object, which might be random or not. The most emblematic example of such a phenomenon is the convergence of a simple random walk, which go left, right, up, or down at each step with probability 1/4 (alternatively randomly wander in a typical American city), toward Brownian motion. This framework nicely intertwine combinatorics with probability theory and allows to wander between the discrete world and the continuous world.

Exposé par Philippe Nadeau: «Classe de cohomologie de la variété de Peterson»

Speaker: Philippe Nadeau
Location: Salle Philippe Flajolet, LIX
Date: Mer. 15 mai. 2019, 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 Philippe Nadeau (Institut Camille Jordan, Université Lyon 1) nous parler de "Classe de cohomologie de la variété de Peterson". 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é: La variété de Peterson est une sous-variété importante de la variété de drapeaux complets, et possède en tant que telle une classe de cohomologie que l'on peut alors développer dans la base des classes de Schubert. Les coefficients sont des entiers négatifs car ils représentent certains nombres d'intersection, mais les déterminer explicitement est délicat avec des méthodes géométriques. Notre but dans ce travail est de donner une interprétation combinatoire pour ces coefficients. Dans cet exposé qui se veut accessible à tous, nous utilisons une approche algébrique et combinatoire pour donner des réponses partielles à ce problème et formuler plusieurs conjectures.
Polynômes de Schubert et mots réduits de permutations jouent des rôles clés. Travail en commun avec Vasu Tewari (UPenn)

Multiplication des grands entiers en O(n log n)

David Harvey et Joris van der Hoeven ont proposé un algorithme de multiplication de grands entiers en O(n log n). Une prépublication est disponible sur HAL; elle est en cours de revue avant publication.

Pour plus d'informations, voir: