Laboratoire d'informatique de l'École polytechnique

News

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)

Exposé par Matthieu Piquerez: «Généralisation des polynômes de Symanzik en dimensions supérieures»

Speaker: Matthieu Piquerez
Location: Salle Philippe Flajolet, LIX
Date: Wed, 24 Apr 2019, 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 Matthieu Piquerez (CMLS, Ecole Polytechnique) nous parler de Généralisation des polynômes de Symanzik en dimensions supérieures. 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 deux polynômes de Symanzik sont des invariants de graphe utilisés en théorie quantique des champs pour calculer des intégrales de Feynman. Le premier polynôme de Symanzik est le dual du polynôme de Kirchhoff pondéré, qui compte le nombre pondéré d'arbres couvrants d'un graphe. En 2009, Duval, Klivans et Martin ont généralisé la notion d'arbre et le théorème de Kirchhoff en dimensions supérieures (sur les complexes simpliciaux). Nous pouvons de même généraliser les polynômes de Symanzik. Les deux polynômes duaux partagent de nombreuses propriétés remarquables, notamment une formule de délétion contraction et une forme déterminantale. Toutefois, nous verrons que la propriété de stabilité par subdivision, propre aux polynômes de Symanzik, rend ces polynômes peut-être plus intéressants que leurs duaux. [arXiv:1901.09797] (https://arxiv.org/abs/1901.09797)

Exposé par Cyril Marzou: «Cartes planaires à degrés prescrits : énumération et limites d'échelle»

Speaker: Cyril Marzou
Location: Salle Philippe Flajolet, LIX
Date: Mer. 17 avr. 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 Cyril Marzouk (IRIF, Université Paris 7) nous parler de Cartes planaires à degrés prescrits : énumération et limites d'échelle. 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 carte planaire finie peut se concevoir comme le recollement topologique de polygones qui forme une sphère ; ainsi, étant donné n polygones, on peut considérer l'ensemble (fini) de tels recollement que l'on peut former. À l'aide d'une bijection avec des arbres étiquetés, nous verrons comment énumérer simplement cet ensemble (dans le cas biparti) et nous étudierons le comportement de la structure de graphe d'une telle carte choisie uniformément au hasard lorsque le nombre n de faces tend vers l'infini. En particulier, nous identifierons l'ordre de grandeur du diamètre et des distances typiques et nous verrons des conditions optimales sur les tailles des polygones pour que l'ensemble des sommets muni de la distance de graphe mise à l'échelle converge en loi vers une limite universelle appelée « carte brownienne ».

Travail disponible en ligne : arXiv:1902.04539 & arXiv:1903.06138.

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:

Talk by Pierre-Louis Poirion: «Random projections for linear and conic programs»

Speaker: Pierre-Louis Poirion
Location: Room Philippe Flajolet, Alan Turing building
Date: Wed, 10 Apr 2019, 14:30-15:30

Pierre-Louis Poirion, who used to be a postdoc in the SYSMO team (now DASCIM), and is now at RIKEN Institute Tokyo, is coming to visit for a couple of weeks, partly supported by the H2020 MINOA project. He is going to give two seminars, both at 14:30 in Salle Philippe Flajolet (2nd floor, left side of the Turing building). The second seminar is entitled Random projections for linear and conic programs.

Abstract: We present a new random projection method that allows the reduction of the number of inequalities of a Linear Program (LP). More precisely, we randomly aggregate the constraints of a LP into a new one with fewer constraints, while approximately preserving the optimal value of the LP. We will also see how to extend this idea to conic programming.

See https://pubsonline.informs.org/doi/10.1287/moor.2017.0894

Talk by Pierre-Louis Poirion: «Algorithms and applications for a class of bilevel MILPs»

Speaker: Pierre-Louis Poirion
Location: Room Henri Poincaré, Alan Turing building
Date: Fri, 5 Apr 2019, 14:00-15:00

Pierre-Louis Poirion, who used to be a postdoc in the SYSMO team (now DASCIM), and is now at RIKEN Institute Tokyo, is coming to visit for a couple of weeks, partly supported by the H2020 MINOA project. He is going to give two seminars, both at 14:30 in Salle Philippe Flajolet (2nd floor, left side of the Turing building). The first seminar is entitled Algorithms and applications for a class of bilevel MILPs.

Abstract: We present a new cut generation algorithm to solve a class of bilevel mixed-integer linear programs where we allow integer variables in the lower level optimization problem. We then apply our methods to the optimal placement of measurement devices in an electrical network.

https://www.sciencedirect.com/science/article/pii/S0166218X18300751

Talk by Kiwon Um: «Physics-based Simulation with Deep Learning»

Speaker: Kiwon Um
Location: Room Nicole-Reine Lepaute (1168)
Date: Wed, 3 Apr 2019, 11:00-12:00

Kiwon Um from the Technical University of Munich will visit us next Wednesday and will give a talk entitled Physics-based Simulation with Deep Learning.

Abstract: Physics-based simulation has been dominant in recreation of a variety of natural phenomena in digital world such as computer-generated imagery. Accordingly, developing an efficient and effective simulation method has been gaining significant attention in the computer graphics community. Despite its significant technical advances, simulations of complex phenomena such as fluid dynamics still remain challenging particularly when it urgently requires both efficiency and accuracy. Recently, a huge amount of accumulated data and its effective use with machine learning have opened the door to many practical solutions for a lot of long-lasting unresolved problems. Along the line of the direction, this talk discusses the use of deep learning techniques with physics-based approaches particularly for fluid simulations in computer graphics. The presenter will introduce an efficient and effective data-driven, i.e., deep learning, method that improves small scale details on top of a traditional liquid simulation method. The experiments of the method will demonstrate how the machine learning successfully improve the target simulation problem together with the physics-based method and carefully refined data. This approach will be further discussed in follow-up projects. Additionally, the presenter will introduce a perceptual evaluation of liquid simulations and its extension to engineering applications. Investigating into its potential, this will be further discussed in conjunction with machine learning.

Soutenance de thèse de Juraj Michalik: «Echantillonage sans remise en Bioinformatique des Acides RiboNucléiques»

Speaker: Juraj Michalik
Location: Amphithéâtre Sophie Germain, Bât. Alan Turing
Date: Fri, 29 Mar 2019, 14:00-16:00

Juraj Michalik soutiendra sa thèse de doctorat, intitulée Échantillonage sans remise en Bioinformatique des Acides RiboNucléiques, le 29 mars 2019 à 14h00 dans l'Amphithéâtre Sophie Germain.

Résumé: Un échantillonnage statistique est central à de nombreuses méthodes algorithmiques pour la bioinformatique structurale des ARNs, où ils sont couramment utilisés pour identifier des modèles structuraux importants, fournir des résumés des espaces de repliement ou approcher des quantités d'intérêt dans l'équilibre thermodynamique. Dans tous ces exemples, la redondance dans l'ensemble échantillonné est non-informative et inefficace, limitant la portée des applications des méthodes existantes. Dans cette thèse, nous introduisons le concept de l'échantillonnage non-redondante et nous explorons ses applications et conséquences en bioinformatique des ARN.

Nous commençons par introduire formellement le concept d'échantillonnage non-redondante et nous démontrons que tout algorithme échantillonnant dans la distribution de Boltzmann peut être modifié en une version non-redondante. Son implémentation repose sur une structure de données spécifique et la modification d'une remontée stochastique pour fournir l'ensemble des structures uniques, avec la même complexité.

Nous montrons alors une exemple pratique en implémentant le principe d'échan- tillonnage non-redondant au sein d'un algorithme combinatoire qui échantillonne des structures localement optimales. Nous exploitons cet outil pour étudier la cinétique des ARN, modélisant des espaces de repliement générés à partir des structures localement optimales. Ces structures agissent comme des pièges cinétiques, rendant leur prise en compte essentielle pour analyser la dynamique des ARN. Des résultats empirique montrent que des espaces de repliement générés à partir des échantillons non-redondants sont plus proches de la réalité que ceux obtenus par un échantillonnage classique.

Nous considérons ensuite le problème du calcul efficace d'estimateurs statistiques à partir d'échantillons non redondants. L'absence de la redondance signifie que l'estimateur naïf, obtenu en moyennant des quantités observés dans l'échantillon, est eronné. Par contre, nous établissons un estimateur non-trivial non-biaisé spécifique aux échantillons non-redondants suivant la distribution de Boltzmann. Nous montrons que l'estimateur des échantillons non-redondants est plus efficace que l'estimateur naïf, notamment dans les cas où la majorité des l'espace de recherche est échantillonné.

Finalement, nous introduisons l'algorithme d'échantillonnage, avec sa contre-partie non-redondante, pour des structures secondaires présentant des pseudonoeuds de type simple. Des pseudonoeuds sont typiquement omis pour des raisons d'efficacité, bien que beaucoup d'entre eux possèdent une grande importance biologique. Nos commençons par proposer une schèma de programmation dynamique qui permet d'énumérer tous les pseudonoeuds composés de deux hélices pouvant contenir des bases non-appariés qui s'entrecroisent. Ce schèma généralise la proposition de Reeders et Giegerich, choisi pour sa base complexité temporelle et spatiale. Par la suite, nous expliquons comment adapter cette décomposition à un algorithme d'échantillonnage statistique pour des pseudonoeuds simples. Finalement, nous présentons des résultats préliminaires et nous discutons sur l'extension de principe non-redondant dnas ce contexte.

Le travail présenté dans cette thèse ouvre non seulement la porte à l'analyse cinétique des séquences d'ARN plus longues, mais aussi l'analyse structurale plus détaillée des séquences d'ARN en général. L'échantillonnage non-redondant peut être employé pour analyser des espaces de recherche pour des problèmes combinatoires susceptibles à l'échantillonnage statistique, y inclus virtuellement tous problèmes solvables par la programmation dynamique. Les principes d'échantillonnage non-redondant sont robustes et typiquement faciles à implémenter, comme démontré par l'inclusion d'échantillonnage non-redondant dans les versions récentes de Vienna package populaire.

Sémin'Ouvert : « Under and over approximated reachability analysis for the verification of control systems », par Sylvie Putot (équipe Cosynus)

Speaker: Sylvie Putot
Location: amphi. Germain (bât. Turing)
Date: Jeu. 21 mars. 2019, 14h30-15h30

This talk will present a class of methods to compute under and over approximating flowpipes for uncertain differential systems, possibly with delays, systems that are pervasive in the modeling of networked control systems. Computing over-approximations of the reachable states has become a classical tool for the safety verification of control systems. Under-approximations are notoriously more difficult to compute, and their use for verification much less studied. I will discuss the guarantees and properties that can be obtained from the joint use of these under and over-approximations for control systems with inputs and disturbances.

Exposé par Pierre Vial: «Exact measures of evaluation in classical natural deduction»

Speaker: Pierre Vial
Location: Salle Philippe Flajolet
Date: Tue, 19 Mar 2019, 14:00-15:00

En plus du séminaire de lundi (Maxime Lucas), nous aurons exceptionnellement un séminaire mardi par Pierre Vial. De par ses thématiques, ce séminaire sera commun avec celui de l'équipe Parsifal.

Résumé: The lambda-mu calculus [Parigot 92] is a computational interpretation of classical natural deduction, which extends the lambda-calculus. We first present non-idempotent intersection and union type systems characterizing head, weak and strong normalization in the lambda-mu calculus. The non-idempotent approach [Gardner 94, de Carvalho 07] provides very simple combinatorial arguments –based on decreasing measures of type derivations– to characterize head and strongly normalizing terms. Moreover, typability provides upper bounds for the lengths of the head, leftmost-outermost and maximal reduction sequences to normal form. Then, building on [Bernadet-Lengrand 13, Accatoli-Kesner-Lengrand 18], we refine these types system to statically obtain the exact measures of the lengths of these three strategies as well as the sizes of the computed normal forms. In contrast to the literature, we define a unique parametrized system, giving rise to optimally factorized proofs, which encapsulates the three evaluation paradigms/notions of normalization. This parametrized approach may be seen as a general methodological contribution to intersection (and union) type theory. The talk will begin with a gentle introduction to intersection type theory, in particular in the non-idempotent case.

Talk by Juliana Freire: «Exploring Big Urban Data»

Speaker: Juliana Freire
Location: Room Gilles Kahn
Date: Mon, 18 Mar 2019, 10:30-15:00

Juliana Freire will give a seminar on Exploring Big Urban Data. It will take place on Monday March 18, from 10.30am to 3pm in Gilles Kahn room.

Abstract: The ability to collect data from urban environments through a variety of sensors, coupled with a push towards openness and transparency by governments, has resulted in the availability of numerous spatio-temporal datasets containing information about diverse components of the cities, including their residents, infrastructure, and the environment. By analyzing the data exhaust from these components, we have the opportunity to better understand how they interact and obtain insights to help address important challenges brought about by urbanization with respect to transportation, resource consumption, housing affordability, and inadequate or aging infrastructure. While there have been successful efforts where data was used to improve operations, policies, and the quality of life for residents, these have been few and far between, because analyzing urban data often requires a staggering amount of work, from identifying relevant data sets, cleaning and integrating them, to performing exploratory analyses over complex, spatio-temporal data.

Our long-term research goal is to enable domain experts to crack the code of cities by freely exploring the vast amounts of urban data. In this talk, I will present methods and systems which combine data management, analytics, and visualization to increase the level of interactivity, scalability, and usability for spatio-temporal data analyses.

Expose de Maxime Lucas: «Higher dimensional rewriting and homotopy»

Speaker: Maxime Lucas
Location: Salle Marcel-Paul Schützenberger
Date: Mon, 18 Mar 2019, 14:00-15:00

Pour le prochain séminaire de l'équipe Cosynus, nous aurons le plaisir d'accueillir Maxime Lucas qui parlera des liens entre réécriture et homotopie.

Résumé: Rewriting theory is traditionally used to study the decidability of equality in various objects. In a seminal paper, Squier made a link between a monoid admitting a presentation which is well-behaved from a rewriting point of view (terminating and confluent in particular), and homotopical properties of this monoid. From this stemmed higher dimensional rewriting theory, which consists in a range of techniques aiming to deduce homotopical information on an object using a well-behaved presentation of this object.

In this talk, we give a general presentation of higher dimensional rewriting applied to monoid and other structures (such as algebras, operads, etc.). We show that (strict) cubical omega-categories form a natural setting in which to express the constructions of higher-dimensional rewriting. In particular, we link the good homotopical properties of the Gray tensor product of cubical omega-categories to the algebraic structure of the local branchings.

Talk by Andrew Ryzhikov: «Synchronizing codes, finite monoids of matrices and unambiguous automata»

Speaker: Andrew Ryzhikov
Location: Room Flajolet
Date: Wed, 13 Mar 2019, 11:00-12:00

The first talk of the next Plateau Saclay Combinatorics Seminar will be given by Andrew Ryzhikov.

Abstract: A set of finite words over a finite alphabet is called a (variable length) code if no word can be represented in two different ways as a concatenation of words from X. A synchronizing word for a code is a word such that every its occurence in a sequence of codewords allows to cut the decoding process in two independent parts before and after the occurence of this word. Synchronizing words allow to stop error propagation in decoding and decode a sequence of codewords from an arbitrary position. I will explain the interplay between synchronizing words in codes, unambiguous automata and finite monoids of zero-one matrices and tell about some old and new results about the bounds on shortest synchronizing words.

This is a joint work in progress with Dominique Perrin.

Talk by Luis Fredes: «Bijections for tree-decorated maps and applications to random maps»

Speaker: Luis Fredes
Location: Room Poincaré
Date: Wed, 13 Mar 2019, 14:00-15:00

The second talk of the next Plateau Saclay Combinatorics Seminar will be given by Luis Fredes.

More details on the seminar web site: https://galac.lri.fr/pages/combi-seminar.html

Abstract: We introduce a new family of maps, namely tree-decorated maps where the tree is not necessarily spanning. To study this class of maps, we define a bijection which allows us to deduce combinatorial results, recovering as a corollary some results about spanning-tree decorated maps, and to understand local limits. Finally, we discuss the possible metric scaling limit of this map: the shocked map. We give certain properties and give the conjectured continuum construction.

This is a work in progress with Avelio Sepúlveda.

Talk by Vincent Laporte: «Jasmin: a workbench for high-assurance low-level programming»

Speaker: Vincent Laporte
Location: LIX, Salle Henri Poincaré
Date: Tue, 12 Mar 2019, 13:30-14:30

Vincent Laporte will give a talk at the Grace seminar on tuesday, march 12 at 13h30 in Salle Henri Poincaré.

Abstract: High-efficiency low-level programming — and in particular the implementation of cryptographic primitives — challenges formal verification methods for correctness and security of the implementations. To overcome this difficulty, the Jasmin language and compiler provide high-level abstractions and predictability of the generated assembly so as to write verifiable efficient low-level programs. The compiler is also formally verified in Coq so as to enable reasoning about functional correctness at the source level. Moreover we’ll present in this talk a proof methodology to enable reasoning about side-channel attack resistance at the source level: building on compiler correctness arguments, we show how to justify preservation, along the compilation process, of the constant-time property.

6 Assistant professor positions open


Application deadline: March 25, 2019
Auditions: between May 13 and May 24, 2019
Anticipated starting date: September 2019

The Department of Computer Science at École Polytechnique welcomes applications for :

  1. three Assistant Professors and one "Monge" assistant professor in Computer Science;
  2. a MONGE assistant professor in Data Science and Artificial Intelligence;
  3. an assistant professor in the Internet of Things. Positions starting September 2019.

The chosen candidates will become a member of the LIX, where they will develop an original research activity in one of the existing teams. Henceforth, candidates must present a scientific project and/or expertise in one of the research domains of the LIX laboratory.

The responsibilities and missions of Assistant Professor positions at Ecole Polytechnique are similar to positions of «Maître de Conférences» in French Universities. Monge positions are tenure-track positions of two times three years, during which the holder of the position will have to pass his «Habilitation à Diriger les Recherches» (habilitation thesis – the holder will benefit from a partial discharge of his teaching duties). After six years, the holder of the Monge position will be tenured as a professor (with responsibilities and missions analogous to the positions of « Professeur des Universités » in France), in case of a positive evaluation from the department committee.

Candidates are invited to contact Eric Goubault (Chair of the Department of Computer Science), François Morain (Vice-Chair of the Department of Computer Science), or Mireille Régnier (Director of LIX), as well as the head(s) of the team(s) most relevant to their research project.

Details can be found here

Requirements

Candidates should hold a Ph.D. and should have demonstrated great ability in research and teaching. They must be able to contribute to computer science education at all teaching level (Bachelor, Ingénieur polytechnicien program, Master of Science and Technology). They will have to show how they will integrate in the teaching teams of basic and more specialized computer courses, and will have to be able to teach at least in one or more of the following domains: algorithmics, programming at all levels (in languages including C++), but also computer architecture, operating systems, compilation, and logic and complexity.

Job 1:

Recruited faculty members will strengthen one of the research teams of the Computer Science Laboratory of the Ecole Polytechnique (LIX) (including ALCO, COMBI, MAX, and AMIBIO for more algorithmic profiles, and COMETE, PARSIFAL and TYPICAL for profiles more related to semantics). Their ability to contribute to project-based teaching, and to strengthen the links between teaching, research and applications, will be an important selection criterion.

Job 2:

The selected candidate will be a member of the Laboratory of Computer Science of the Ecole Polytechnique (LIX), where she or he will develop an original research activity in one of the following teams: DATASCIM, CEDAR ou STREAM. Candidates must present a scientific project and / or expertise in data science and artificial intelligence.

Job 3:

The selected candidate will be a member of the Laboratory of Computer Science of the Ecole Polytechnique (LIX), where she or he will develop an original research activity in the « Networks » team. Candidates must present a scientific project and / or expertise in relation to IoT.

Details here and there.