Laboratoire d'informatique de l'École polytechnique

News

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.

Exposé par Anand Kumar Narayanan: «Fast computation of isomorphisms between finite fields using elliptic curves»

Speaker: Anand Kumar Narayanan
Location: Salle Grace Hopper
Date: Wed, 6 Mar 2019, 14:00-15:00

Le mercredi 6 mars à 14h00, l'équipe MAX aura le plaisir d'accueillir Anand Kumar Narayanan pour son exposé intitulé «Fast computation of isomorphisms between finite fields using elliptic curves».

Pour plus d'informations, voir:

http://www.lix.polytechnique.fr/max/max-web/max/max-seminar.fr.html

Talk by Antoine Deza: «Algorithmic, combinatorial, and geometric aspects of linear optimization»

Speaker: Antoine Deza
Location: Salle Philippe Flajolet
Date: Mon, 4 Mar 2019, 14:30-15:30

Antoine Deza, professor at McMaster University (CA) will give a DASCIM seminar at LIX, in Salle Philippe Flajolet, at 14:30.

Abstract: The simplex and interior point methods are currently the most computationally successful algorithms for linear optimization. While the simplex methods follow an edge path, the interior point methods follow the central path. The algorithmic issues are closely related to the combinatorial and geometric structure of the feasible region. Focusing on the analysis of worst-case constructions leading to computationally challenging instances, we discuss connections to the largest diameter of lattice polytopes, to the complexity of convex matroid optimization, and to the number of generalized retarded functions in quantum field theory. Complexity results and open questions are also presented. In particular, we answer a question raised in 1986 by Colbourn, Kocay, and Stinson by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive.

Based on joint works with Anna Deza (Toronto), Joe Guan (McMaster), Asaf Levin (Technion), George Manoussakis (Versailles), Syed Meesum (Wrocław), Shmuel Onn (Technion), and Lionel Pournin (Paris XIII).

Soutenance de thèse de Konstantinos Skianis

Speaker: Konstantinos Skianis
Location: Amphi Sophie Germain
Date: Fri, 1 Mar 2019, 16:00-18:00

Konstantinos Skianis soutiendra sa thèse intitulée «Nouvelles représentations, la régularisation et les distances pour la classification de texte», le Vendredi 01 Mars 2019 à 16h00, dans l'amphithéâtre Sophie Germain.

Résumé: Le texte a été le moyen dominant de stockage de données dans des systèmes informatiques et d’ envoi d informations sur le Web. Extraire du texte des représentations significatives a été un élément clé pour la modélisation de langage. Le but de cette thèse est d étudier les problèmes liés au traitement du langage naturel, comme l' apprentissage de la représentation, la régularisation de la classification des textes et la mesure de la distance entre les documents. Dans la première partie de la thèse, nous avons étudié de nouvelles représentations à base de graphes pour le texte. Nous avons introduit ICW, une nouvelle métrique basée sur des graphiques au niveau de la collection afin de pénaliser les nœuds centraux, un peu comme l'IDF. Les rendements de TW-ICW et TW- ICW-LW sont comparables à ceux des classificateurs d apprentissage en profondeur les plus récents pour la tâche de classification du texte. Dans la deuxième partie de la thèse, nous nous sommes concentrés sur la régularisation pour le problème de l apprentissage supervisé et plus spécifiquement pour la tâche de la classification du texte. Nous avons d abord examiné comment divers groupes linguistiques existants peuvent aider de simples modèles de régression logistique pour la catégorisation de texte. Nous avons ensuite conçu une nouvelle version superposée de l’ algorithme Orthogonal Matching Pursuit, une technique de sélection de variables gloutonne bien connue. Dans la dernière partie de la thèse, nous étudions la mesure des distances entre les documents. Nous avons d abord examiné les méthodes rapides permettant d accroître la distance du populaire Word Mover ‘s Distance. Enfin, nous avons travaillé sur de nouvelles méthodes de graphes supervisés pour le calcul de la distance.

Talk by Sebastian Will: «Infrared: Targeting Multiple Complex Features in Positive Design Tasks»

Speaker: Sebastian Will
Location: Room Philippe Flajolet
Date: Thu, 28 Feb 2019, 14:30-15:30

AMIBio is pleased to welcome Sebastian Will (University of Vienna) next Thursday 28/02, 14h30, at LIX in room Philippe Flajolet.

Abstract: Designing (i.e. generating) objects with highly specific properties is a fundamental task with broad applications. For example, for biotechnological applications it is desirable to design sequences of biological macromolecules (RNAs or proteins) such that the molecules adopt specific target structures. This task is generally known as negative design, since the designed sequences must avoid favorable energies for all structures but the one or multiple target structures themselves. In contrast, positive design aims exclusively at favorable energies of the target structures; typically this supports the negative design objectives as well. Infrared abstracts such positive design tasks as the generation of objects with multiple highly specific complex properties. This generalization enables applying general algorithmic methods like the modeling as constraint networks and the targeting of specific feature values by multi-dimensional Boltzmann sampling. This method allows generating distributions that are narrowly centered around targeted feature values, such that satisfying complex properties becomes effective. The method is ultimately based on dynamic programming over tree decompositions that generates Boltzmann distributed samples efficiently with respect to the treewidth due to the targeted features. After outlining the methods in Infrared as well as the modeling based on the Infrared library, I present results from our Infrared-based implementation of positive RNA design "RNARedprint v2", which can simultaneously target specific energies of multiple RNA structures. Finally, I discuss other applications of the design framework in Infrared, specifically the generation of complex background models.

Exposé par Jérémy Ledent: «A topological model for dynamic epistemic logic»

Speaker: Jérémy Ledent
Location: Salle Philippe Flajolet
Date: Wed, 27 Feb 2019, 14:00-15:00

Pour le prochain séminaire de l'équipe Cosynus, nous aurons le plaisir d'accueillir Jérémy Ledent qui nous parlera de logique épistémique.

Résumé: Epistemic logic is the logic of knowledge; it studies what a set of agents know about the world and about each other. The usual model for multi-agent epistemic logic S5 is based on a Kripke frame, which is a graph whose edges are labeled with agents that do not distinguish between two states. We show that this structure is related to the chromatic simplicial complexes that are used in the topological approach to distributed computability. This allows us to view the input, output and protocol complexes as models of epistemic logic, on which we can interpret formulas saying what the processes know about the system. We then extend this duality to the setting of dynamic epistemic logic in order to describe how the epistemic model evolves when communication happens between the agents. By doing so, we are able to prove impossibility results for task solvability, using logical arguments.

Exposé par Matthieu Josuat-Vergès: «Des tresses aux amas via la dualité de Koszul»

Speaker: Matthieu Josuat-Vergès
Location: Salle Philippe Flajolet
Date: Wed, 27 Feb 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 Josuat-Vergès (UPEM) nous donner un exposé sur "Des tresses aux amas via la dualité de Koszul". 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é: Il est bien connu que le groupe de tresses admet une présentations avec des générateurs qui satisfont les relations de tresses. On peut voir ces générateurs comme échangeant deux brins voisins du point de vue géométrique. Une autre présentation, due à Birman, Ko, Lee, consiste à regarder un ensemble plus gros de générateurs (ils correspondent alors à toutes les transpositions et pas seulement aux transpositions simples). Un problème d'énumération des tresses selon leur longueur (nombre de facteurs dans une expression en termes de produits de générateurs) fait intervenir les partitions non-croisées et leur fonction de Möbius, d'après des résultats de Albenque et Nadeau. Après avoir introduit ces résultats, nous expliquerons pourquoi ceci mène à considérer la notion de dual de Koszul, et pourquoi cette dualité fait un lien avec le complexe d'amas. Nous éviterons les détails techniques, en particulier on ne considèrera que le cas du groupe symétrique bien qu'en général le cadre est celui des groupes finis de réflexions. Il s'agit d'un travail en commun avec Philippe Nadeau.

Sémin'Ouvert : « Les codes algébriques et leurs algorithmes de décodage en liste », par Alain Couvreur (équipe Grace)

Speaker: Alain Couvreur
Location: salle G. Kahn (bât. Turing)
Date: Jeu. 21 févr. 2019, 14h30-15h30

Cet exposé introductif présentera les notions élémentaires de théorie des codes correcteurs d'erreurs et les constructions de ces objets à partir de polynômes. On s'intéressera ensuite aux algorithmes de décodage associés à ces codes et présentera les avancées majeures des deux dernières décennies sur le sujet, en particulier les travaux de Sudan et Guruswami sur le problème du décodage en listes.

Séminaire Cosynus: exposés par Goran Frehse et Mirco Giacobbe

Pour le prochain séminaire de l'équipe Cosynus, nous aurons le plaisir d'accueillir Goran Frehse et Mirco Giacobbe qui nous parleront d'atteignabilité. Les deux exposés se suivent et devraient durer 30 minutes chacun.

Goran Frehse -- Reach Set Approximation through Decomposition with Low-dimensional Sets and High-dimensional Matrices

Abstract: Approximating the set of reachable states of a dynamical system is an algorithmic yet mathematically rigorous way to reason about its safety. Although progress has been made in the development of efficient algorithms for affine dynamical systems, available algorithms still lack scalability to ensure their wide adoption in the industrial setting. While modern linear algebra packages are efficient for matrices with tens of thousands of dimensions, set-based image computations are limited to a few hundred. We propose to decompose reach set computations such that set operations are performed in low dimensions, while matrix operations like exponentiation are carried out in the full dimension. Our method is applicable both in dense- and discrete-time settings. For a set of standard benchmarks, it shows a speed-up of up to two orders of magnitude compared to the respective state-of-the art tools, with only modest losses in accuracy. For the dense-time case, we show an experiment with more than 10.000 variables, roughly two orders of magnitude higher than possible with previous approaches.

Goran Frehse received a Diploma in electrical engineering and information technology from Karlsruhe Institute of Technology and a PhD in computer science from Radboud University Nijmegen. From 2006 to 2018, he was an associate professor at the University Grenoble Alpes, holding a research fellowship (chaire) from 2016. Since 2018, he is an associate professor at ENSTA ParisTech. He is the architect and lead developer of two well-known model checking tools for hybrid and cyber-physical systems, PHAVer and SpaceEx.

Mirco Giacobbe -- Refining Template-polyhedra from Counterexamples

Abstract: Template polyhedra generalize intervals and octagons to polyhedra whose facets are normal to arbitrary sets of directions. They are successfully employed by SpaceEx in the reachability analysis of hybrid automata. While previously, the choice of directions has been left to the user, this talk presents a method for the automatic discovery of directions that generalize and eliminate spurious counterexamples. The method applies to linear and nonlinear hybrid automata with constant derivatives, and to hybrid automata with linear ODE. Our experiments demonstrate its efficacy on the time-unbounded reachability of several benchmarks.

Mirco Giacobbe received BSc and MSc from the University of Trento and MSc from RWTH AAchen, in computer Science. Today he is a PhD student in Henziger’s group, at IST Austria. His work focuses on the analysis of timed and hybrid systems and on the application of formal methods in artificial intelligence and systems biology.

Exposé par Anaël Grandjean: «L-Convex Polyominoes are Recognizable in Real Time by 2D Cellular Automata»

Speaker: Anaël Grandjean
Location: Salle Henri Poincaré
Date: Mer. 20 févr. 2019, 11h00-12h00

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 11h dans la salle Henri Poincaré du LIX (au rez-de-chaussée, aux 3/4 du corridor, sur la gauche). Il s'agit d'un séminaire joint avec l'équipe AlCo. Nous aurons le plaisir d'écouter Anaël Grandjean (Université de Créteil) nous donner un exposé sur «L-Convex Polyominoes are Recognizable in Real Time by 2D Cellular Automata». 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é: This is a joint work with Victor Poupet where we investigate the recognition power of cellular automata in real time. A polyomino is said to be L-convex if any two of its cells are connected by a 4-connected inner path that changes direction at most once. The 2-dimensional language representing such polyominoes has been recently proved to be recognizable by tiling systems by S. Brocchi, A. Frosini, R. Pinzani and S. Rinaldi. In an attempt to compare recognition power of tiling systems and cellular automata, we have proved that this language can be recognized by 2-dimensional cellular automata working on the von Neumann neighborhood in real time. Although the construction uses a characterization of L-convex polyominoes that is similar to the one used for tiling systems, the real time constraint which has no equivalent in terms of tilings requires the use of techniques that are specific to cellular automata.

Talk by Amina Doumane: «Completeness for identity-free Kleene Lattices»

Speaker: Amina Doumane
Location: Room Grace Hopper
Date: Tue, 19 Feb 2019, 14:00-15:00

Amina Doumane (ENS Lyon) will speak at the Parsifal seminar on Tuesday, February 19th, at 14h00 in room Schützenberger.

Abstract: We provide a finite set of axioms for identity-free Kleene lattices, which we prove sound and complete for the equational theory of their relational models. Our proof builds on the completeness theorem for Kleene algebra, and on a novel automata construction that makes it possible to extract axiomatic proofs using a Kleene-like algorithm.

Talk by Quentin Galvane: «From Virtual Cinematography to Autonomous Drone Videography»

Speaker: Quentin Galvane
Location: Room Henri Poincaré
Date: Tue, 12 Feb 2019, 11:00-12:00

Quentin Galvane from INRIA Rennes will give a talk in STREAM group meeting today at 11am (Salle Henri Poincaré, RdC), entitled: "From Virtual Cinematography to Autonomous Drone Videography".

Abstract: Focusing on camera placement, camera motion and automatic editing in virtual environments, the field of virtual cinematography has triggered the interest of the movie industry for many applications, including real world shooting with Unmanned Aerial Vehicles. In this talk I will present different virtual cinematography techniques that were extented to drone videography. These solutions aim at offering a high-level control of cinematographic drones to automatically or interactively plan drone motions in dynamic 3D environments while satisfying cinematographic constraints.

Exposé par Sergey Dovga: «Asymptotic distribution of parameters in random maps»

Speaker: Sergey Dovgal
Location: Salle Philippe Flajolet
Date: Mer. 6 févr. 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 Sergey Dovgal (LIPN, Université Paris 13) nous donner un exposé sur «Asymptotic distribution of parameters in random maps». Le résumé est disponible ci-dessous.

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

Abstract: In this joint work with Olivier Bodini, Julien Courtiel, and Hsien-Kuei Hwang, we consider random rooted maps without regard to their genus. We address the problem of limiting distributions for six different parameters:

  • vertices
  • leaves
  • loops
  • root edges
  • root isthmic constructions
  • root vertex degree

Each parameter has a different limiting distribution, varying from (discrete) geometric and Poisson to (continuous) Beta, normal, uniform, and an unusual bounded distribution characterised by its moments.

Olivier Bournez récompensé par le prix La Recherche 2019

Olivier Bournez, et ses co-auteurs, se sont vus attribué le prix La Recherche 2019, mention Sciences de l'information pour leur publication «Strong Turing Completeness of Continuous Chemical Reaction Networks and Compilation of Mixed Analog-Digital Programs».

La remise du prix se déroulera le 13 février 2019 à l'université Paris-Dauphine.

Pour plus d'informations, voir la page Prix La Recherche 2019 - 15e édition sur le site du magazine La Recherche.

Talk by Fei Song: «Anomaly Detection and Explanation Discovery on Event Streams»

Speaker: Fei Song
Location: Thomas Flowers room, Turing building
Date: Fri, 1 Feb 2019, 14:00-15:00

Fei Song will present his 2018 BIRTE paper on February 1st (Friday), 2pm. The talk will take place in the Thomas Flowers room, Turing building.

Abstract: As enterprise information systems are collecting event streams from various sources, the ability of a system to automatically detect anomalous events and further provide human readable explanations is of paramount importance. In this position paper, we argue for the need of a new type of data stream analytics that can address anomaly detection and explanation discovery in a single, integrated system, which not only offers increased business intelligence, but also opens up opportunities for improved solutions. In particular, we propose a two-pass approach to building such a system, highlight the challenges, and offer initial directions for solutions

Talk by Michael Neff: «Computational Approaches to Nonverbal Communication: Personality Synthesis and Interaction in Embodied VR»

Speaker: Michael Neff
Location: Room Henri Poincaré
Date: Tue, 29 Jan 2019, 11:00-12:00

Michael Neff (Motion Lab, University of California, Davis) will give a talk in STREAM group meeting tomorrow at 11am (Salle Henri Poincaré, RdC), entitled: Computational Approaches to Nonverbal Communication: Personality Synthesis and Interaction in Embodied VR»

Abstract: This talk will discuss two different bodies of work. The first part of the talk will examine how nonverbal communication, and in particular gesture, conveys personality to observers. Our work is framed using the Five Factor or OCEAN model of personality from social psychology. Drawing both from the psychology literature and primary perceptual research, I'll show how movement changes impact perceived character personality. I'll look at particular movement changes that influence personality traits and also show that in many cases, people may be making two distinct personality judgments, rather than five, as would be expected for the five factor personality model. The second part of the talk will focus on how people interact in virtual reality when provided with motion tracked avatars. I'll discuss a study that compared interaction in VR with embodied avatars, interaction in a shared VR environment, but no avatars, and face-to-face interaction. Interestingly, the embodied VR condition performed comparably to face-to-face social interaction on a range of measures, including social presence and conversational turn length.

Bio: Michael Neff is a professor in Computer Science and Cinema & Digital Media at the University of California, Davis where he leads the Motion Lab, an interdisciplinary research effort in character animation and embodied interaction. He holds a Ph.D. from the University of Toronto and is also a Certified Laban Movement Analyst. His interests include character animation, especially modeling expressive movement, nonverbal communication, gesture and applying performing arts knowledge to animation. He received an NSF CAREER Award, the Alain Fournier Award for his dissertation, two best paper awards and the Isadora Duncan Award for Visual Design. He is past Chair of the Department of Cinema and Digital Media.

Mini course by Ioana Manolescu: «Content Management Techniques for Fact-Checking»

Speaker: Ioana Manolescu
Location: Room Grace Hopper
Date: Mon, 28 Jan 2019, 14:00-17:30

The first mini course for PhD students will happen on Monday, January 28, 14h - 17h30 (with a break in the middle), in the Grace Hopper room. The lecturer is Ioana Manolescu who will speak about: Content Management Techniques for Fact-Checking.

These mini-courses are intended for PhD students and introduce to the various fields of research developed in the laboratory.

Talk by Dimitrios Letsios: «Data-Driven Optimization for Efficient Resource Allocation in Industrial Applications»

Speaker: Dimitrios Letsios
Location: Room Philppe Flajolet, LIX
Date: Tue, 22 Jan 2019, 14:30-15:30

Dr. Dimitrios LETSIOS, currently postdoctoral fellow at the Department of Computing (DoC) at Imperial College London, will give a seminar on Tue, Jan 22 at 14:30-15:20 in Salle Philppe Flajolet (in front of Vanessa's office on the second floor).

Abstract: Machine learning and data science methodologies leverage historical data to produce powerful models approximating unknown functions and predicting uncertain parameters. Mathematical optimization offers strong modeling paradigms, algorithms, and solvers for solving complex decision-making problems with analytical methods. This talk shall present approaches for combining machine learning and data science models with mathematical optimization methods, in a unified setting, towards effective resource allocation. The goal is the design of tailor-made, exact optimization methods exploiting the structure of predictive model outcomes. We shall discuss using gradient-boosted trees (GBTs) to approximate unknown functions and solving new optimization problems with trained GBTs embedded for reducing the energy consumption in industrial processes. We shall also discuss using robust combinatorial optimization with uncertainty sets obtained from data for effective production planning and scheduling. Finally, the talk shall present applications of the proposed approaches and numerical results with real data.

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.

Talk by Benoît Groz: «Exploring multidimensional data through skylines: computing and sampling skylines»

Speaker: Benoît Groz
Location: Thomas Flowers room
Date: Mon, 21 Jan 2019, 14:00-15:00

The Cedar team has scheduled a seminar on January 21st by Benoît Groz.

Title: Exploring multidimensional data through skylines: computing and sampling skylines

Abstract: In everyday life, users often wish to order data items according to multiple criteria. As those multiple orders need not be correlated in general, there generally is no single best item. As a consequence, the set of pareto optima - the skyline of the set - has proved popular to identify the items that are most relevant for the criteria specified. However, filtering items through skylines has some limitations: computing skylines can be computationally intensive, and the skyline may not be very selective. We outline approaches that we developed to address those 2 issues:

- we propose algorithms to compute skylines efficiently in a

probabilistic setting where items can only be compared through a random oracle (a simplistic model for crowdsourcing scenarios).

- we investigate algorithms to sample skylines when we are given a set of

points in "R^d" together with a value "k", and we wish to compute a set of "k" points maximizing the volume dominated by the sample.

Talk by Oana Balalau: «On Capturing Structure and Semantics in Graphs and Text»

Speaker: Oana Balalau
Location: Thomas Flowers room, Alan Turing building
Date: Fri, 18 Jan 2019, 14:00-15:00

Oana Balalau, currently a post-doc at MPI Germany, will give a seminar on Jan 18, 2019, at 2 pm, in the Flowers room.

ABstract: Graphs can model a variety of datasets, spanning from social networks to text. Because of the diversity and relevance of applications, it is important to develop algorithms that are well-suited for mining real-world graphs. In this talk, I will give several results on mining dense subgraphs, where density is used to measure the importance and the cohesiveness of a subgraph. Next, I will demonstrate how dense subgraphs can be used for real-world disaster detection. For this purpose, we construct representative graphs from informal text, such as posts from the social media platform Twitter. Social media differ from traditional media through an important characteristic: every user can contribute to a story with its own personal experience. This richness of content can help in a situation of crisis when authorities want to access more information about affected areas.

Lastly, I will discuss text mining in another social media platform, the online forum Reddit. Discussions on online forums are the result of both the dynamics of a conversation and the features of the underlying platform. My focus in this work is on finding patterns in conversations and on developing new tools that better capture the semantics of an online discussion.

Sémin'Ouvert : « A couple of stories on energy and mathematical optimization » par Leo Liberti (équipe Dascim)

Speaker: Leo Liberti
Location: salle G. Kahn (bât. Turing)
Date: Jeu. 17 janv. 2019, 14h15-15h15

I will sketch the interaction between the field of mathematical optimization and some problems arising in energy management. I will start with a short tutorial on mathematical optimization. I shall then discuss the problem of monitoring an electrical grid. If I have time, I shall go on to discuss operating it and forecasting its production.

PhD and Industry Days 2019

This 2-day meeting will give a panorama of the current challenges that the transition to renewable sources of energy is bringing to the industrial sector. There will be talks on optimization and equilibrium models, both from industrial partners and academic colleagues. Registration is free, but to organize the logistics we ask to REGISTER HERE and let us know which days you plan to attend the meeting -- BEFORE MONDAY 14 JAN 2019.

Talk by Georg Struth: «Generalised Kripke Semantics for Concurrent Quantales»

Speaker: Georg Struth
Location: Room Grace Hopper
Date: Mon, 14 Jan 2019, 15:00-16:00

For the next seminar of the Cosynus team, we will have the pleasure of welcoming Georg Struth.

Abstract: I present ongoing work on a new technique for constructing models of concurrent quantales (and concurrent Kleene algebras). It is inspired by modal correspondence theory for substructural logics and the duality between boolean algebras with operators and relational structures. In our case, frame conditions are given by ternary relations. The operations of concurrent quantales arise as binary modalities---in fact as convolution operations---over quantale-valued functions, parametrised by the ternary frames. The main result so far is a correspondence between concurrent quantales and frame conditions. A first example constructs concurrent quantales and Kleene algebras of weighted shuffle languages from word-level concatenations and shuffles. The second one obtains concurrent quantales of graphs (or graph types) by lifting from the operations of complete join and disjoint union on graphs. Concurrent quantales of pomset languages arise as special cases. Similar constructions in separation logic or interval temporal logics illustrate the universality of the approach, if time permits. Joint work with James Cranch, Simon Doherty, Brijesh Dongol and Ian Hayes