Laboratoire d'informatique de l'École polytechnique

News

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

Talk by Louis Jachiet: «On the Optimization of Recursive Relational Queries»

Speaker: Louis Jachiet
Location: Room Flowers, Alan Turing building
Date: Fri, 11 Jan 2019, 14:00-15:00

Louis Jachiet will give a talk on Friday 11th January, at 2pm. The talk will take place in the Turing building, Inria Saclay, in the room Flowers.

Abstract:

The relational model has benefited from a huge body of research in the last half century. Since its introduction, the relational model has seen various attempts to extend it with recursion and it is now possible to use recursion in several SQL or Datalog database systems. The optimization of recursive queries remains, however, a challenge.

In this talk, we introduce μ-RA, a variation of the Relational Algebra that allows for the expression of relational queries with recursion. μ-RA can express unions of conjunctive regular path queries as well as certain non-regular properties. We present its syntax, semantics and the rewriting rules we specifically devised to tackle the optimization of recursive queries. We will also present our experiment to compare our prototype implementation of these rewriting rules with respect to state-of-the-art systems.

Séminaire Combi: exposés par Aaron Lauve et Noam Zeilberger

Speaker: Aaron Lauve et Noam Zeilberger
Location: Salle Flajolet, LIX
Date: Wed, 9 Jan 2019, 11:00-15:00

Ce mercredi, le séminaire Combi propose 2 exposés :

  • à 11h en salle Flajolet, Generalized Jucys-Murphy elements and canonical idempotents in towers of algebras par Aaron Lauve de l'université de Loyola

  • à 14h en salle Poincaré, séminaire joint avec Parsifal, A proof-theoretic analysis of the rotation lattice of binary trees par Noam Zeilberger, postdoc à Parsifal.

Les résumés sont disponibles ci-dessous.

Generalized Jucys-Murphy elements and canonical idempotents in towers of algebras

The collection of symmetric group algebras serves as a motivating example for what I'll call a multiplicity-free tower of finite dimensional algebras. Any such family has a canonical complete set of pairwise orthogonal primitive idempotents stemming from its representation theory. In the case of the symmetric group algebras, these idempotents were first given a tidy formula by Thrall (1941) using the infamous "Young symmetrizers." I'll provide other examples (Brauer algebras will feature prominently), then highlight several methods to compute these idempotents, extending work of Jucys, Murphy, and Vershik--Okunkov. Opportunities for SageMath projects will be littered throughout. (Based on work with S. Doty and G.H. Seelinger, arXiv:1606.08900.)

A proof-theoretic analysis of the rotation lattice of binary trees

The classical Tamari lattice Yn is defined as the set of binary trees with n internal nodes, with the partial ordering induced by the (right) rotation operation. It is not obvious why Yn is a lattice, but this was first proved by Haya Friedman and Dov Tamari in the late 1950s. More recently, Frédéric Chapoton discovered another surprising fact about the rotation ordering, namely that Yn contains exactly 2(4n + 1)!/((n + 1)!(3n + 2)!) pairs of related trees. (Even more surprising was how Chapoton discovered this formula: via the Online Encyclopedia of Integer Sequences, because the formula had already been computed in the early 1960s by Bill Tutte, but for a completely different family of objects!)

In the talk I will describe a new way of looking at the rotation ordering that is motivated by old ideas in proof theory. This will lead us to systematic ways of thinking about:

  1. the lattice property of Yn, and
  2. the Tutte-Chapoton formula for the number of intervals in Yn.

No advanced background in either proof theory or combinatorics will be assumed.

Soutenance de thèse de Dorian Nogneng: «Correspondances non rigides entre surfaces plongées en 3D»

Speaker: Dorian Nogneng
Location: Salle Gilles Kahn, Bât. Alant Turing
Date: Fri, 21 Dec 2018, 14:00-16:00

Dorian Nogneng soutiendra sa thèse intitulée Correspondances non rigides entre surfaces plongées en 3D le 21 décembre 2018 à 14h00 dans la salle Gilles Kahn.

Anniversaire du LIX

Location: LIX
Date: Thu, 20 Dec 2018, 10:00-17:00
Le LIX fête ses 30 ans le 20 décembre 2018 !
Voir l'événement.
Télécharger l'invitation.

Exposé par Audrey Legendre: «Programmation mathématique multi-objectif pour la prédiction de structures secondaires d'ARN et de complexes d'ARN»

Speaker: Audrey Legendre
Location: Salle Flajolet, bât. Alan Turing
Date: Thu, 13 Dec 2018, 14:30-15:30

Cette semaine, le séminaire BioInfo accueillera Audrey Legendre (Université d'Evry / Université Paris-Saclay). Le séminaire se tiendra à 14h30 en salle Flajolet au LIX.

Résumé : La prédiction de structure d'ARN est une tâche difficile. En effet les structures prédites par les outils de la littérature, qui dans la plupart des cas se basent sur un modèle de prédiction unique, ne correspondent pas toujours à la structure réelle. Nous nous intéres- sons plus particulièrement à la prédiction de la structure secondaire des ARN ainsi que des complexes d'ARN. Dans le but d'améliorer la qualité de prédiction de ces structures, nous développons des algorithmes qui: i) prédisent les k-meilleures structures, ii) combinent plusieurs modèles de prédiction en l’utilisant la programmation mathématique linéaire, iii) peuvent prendre en compte des contraintes utilisateurs.

Talk by Pedro Borges: «Smooth Approximations of Optimal Value Reformulations of Convex Subproblems»

Speaker: Pedro Borges
Location: Room Flajolet, Alan Turing building
Date: Tue, 11 Dec 2018, 11:00-12:00

We are please to announce a seminar by Pedro Borges (IMPA, Rio de Janeiro) on Tuesday 11th December at 14h00, in the Flajolet room at LIX. The title of the seminar is Smooth Approximations of Optimal Value Reformulations of Convex Subproblems

Pedro is a PhD student of Claudia Sagastizabal and they are both spending 4 months (Dec 2018-March 2019) at LIX thanks to the Gaspard Monge Visiting Professor Program of the Fondation de l'Ecole polytechnique.

Soutenance de thèse de Guillaume Cordonnier: «Modèles à couches pour simuler l'évolution de paysages à grande échelle»

Speaker: Guillaume Cordonnier
Location: Amphi Sophe Germain, Bât. Alan turing
Date: Thu, 6 Dec 2018, 14:30-16:30

Guillaume Cordonnier, de l'équipe Stream soutiendra sa thèse, intitulée «Modèles à couches pour simuler l'évolution de paysages à grande échelle», le 6 décembre à 14h30 dans l'amphi Sophie Germain, bâtiment Alan Turing, sur le campus de l'Ecole Polytechnique.

Le jury sera composé de:

  • Pierre Poulin, Université de Montréal ( Rapporteur )
  • Jean-Michel Dischler, Université de Strasbourg ( Rapporteur )
  • François Sillion, Inria ( Examinateur )
  • Bedrich Benes, Purdue University ( Examinateur )
  • Jean Braun, GFZ German Research Center for Geosciences ( Examinateur )
  • Marie-Paule Cani, Ecole Polytechnique ( Directrice de thèse )
  • Eric Galin, Université de Lyon ( Co-directeur de thèse )

Résumé: Le développement des nouvelles technologies permet la visualisation interactive de mondes virtuels de plus en plus vastes et complexes. La production de paysages plausibles au sein de ces mondes est un défi, dont l'importance est attesté par l'ubiquité des éléments de terrain et des écosystèmes, et leur implication dans la qualité du résultat. S'y rajoute la difficulté d'éditer de tels éléments sur des échelles spatiales et temporelles aussi vastes que peuvent l'être celles des chaînes de montagnes. Cette édition se fait souvent en couplant des méthodes manuelles et de longues simulations numériques dont le calibrage est complexifié par le nombre des paramètres et leur caractère peu intuitif.

Je propose dans cette thèse d'explorer de nouvelles méthodes de simulation de paysages à grande échelle, avec pour objectif d'améliorer le contrôle et le réalisme des scènes obtenues. Notre stratégie est de fonder nos méthodes sur des lois éprouvées dans différents domaines scientifiques, ce qui permet de renforcer la plausibilité des résultats, tout en construisant des outils de résolution efficaces et des leviers de contrôles intuitifs.

En observant des phénomènes liés aux zones de compression de la croûte terrestre, nous proposons une méthode de contrôle intuitif de la surrection à l'aide d'une métaphore de sculpture des plaques tectoniques. Combinée avec de nouvelles méthodes efficaces d'érosion fluviale et glaciaire, celle-ci permet de sculpter rapidement de vastes chaînes de montagnes. Pour visualiser les paysages obtenus à échelle humaine, nous démontrons le besoin de combiner la simulation de phénomènes variés et de temporalités différentes. Nous proposons une méthode de simulation stochastique pour résoudre cette difficile cohabitation, que nous appliquons à la simulation de processus géologiques tels que l'érosion, jointe à la formation d'écosystèmes. Cette méthode est déclinée sur GPU et appliquée à la formation du manteau neigeux, en combinant des aspects au long cours (précipitations, changements d'état de l'eau) et des aspects dynamiques (avalanches, impact des skieurs).

Les différentes méthodes proposées permettent de simuler l'évolution de paysages à grande échelle, tout en accordant une attention particulière au contrôle. Ces aspects sont validés par des études utilisateur et des comparaisons avec des données issues de paysages réels.

Séminaire Combi: exposés par Friedrich Wehrun et Alina Mayorova

Speaker: Friedrich Wehrun et Alina Mayorova
Location: Salle Flajolet, LIX
Date: Wed, 5 Dec 2018, 11:00-16:00

Ce mercredi, nous aurons 2 exposés dans le cadre du séminaire Combi:

  • à 11h00, Friedrich Wehrung (Université de Caen) nous parlera de La théorie équationnelle de l’ordre faible de Bruhat

  • à 15h00, Alina Mayorova (Ecole Polytechnique) nous parlera de Type B extensions of Cauchy identity and Schur-positivity related to Chow’s quasisymmetric functions.

Les résumés sont disponibles ci-dessous et sur le site du séminaire : https://galac.lri.fr/pages/combi-seminar.html

La théorie équationnelle de l’ordre faible de Bruhat

Ceci est un travail joint avec Luigi Santocanale.

Il est connu que pour tout entier naturel n, le groupe symétrique d’ordre n peut être muni d’une structure de treillis, souvent appelé le permutoèdre sur n lettres P(n), qui est aussi l’ordre faible de Bruhat de type A_{n-1}. Björner et Wachs ont montré que le treillis de Tamari A(n) est un rétracte, pour la structure de treillis, de P(n). Par suite, toute identité (« loi ») de théorie des treillis, valide dans tous les P(n), est également valide dans tous les A(n). La réciproque est fausse, car il existe une identité valide dans tous les A(n) mais non valide dans P(4).

La théorie équationnelle de tous les P(n), c’est à dire l’ensemble de toutes les identités satisfaites par tous les P(n), est décidable. Un résultat similaire est valide pour tous les A(n), ou des classes plus générales de treillis Cambriens de type A. La théorie équationnelle de tous les P(n) n’est pas triviale: il existe une identité (à 15 variables) valide dans tous les P(n), mais non satisfaite par un certain treillis à 3338 éléments.

Références :

  • Luigi Santocanale et Friedrich Wehrung, Sublattices of associahedra and permutohedra, Advances in Applied Mathematics 51, no. 3 (2013), 419--445.
  • Luigi Santocanale et Friedrich Wehrung, The equational theory of the weak Bruhat order on finite symmetric groups, Journal of the European Mathematical Society 20, no. 8 (2018), 1959--2003

The Cauchy identity is a fundamental formula in algebraic combinatorics that captures all the nice properties of the RSK correspondence. In particular, expanding both sides of the identity with Gessel's quasisymmetric functions allows to recover the descent preserving property, an essential tool to prove the Schur positivity of sets of permutations. We introduce a new type B extension of Schur-positivity based on Chow's quasisymmetric functions and domino functions, i.e. generating functions for domino tableaux. Further, we suggest a q-analogue of the modified domino functions to extend a type B Cauchy identity by Lam and link it with Chow's quasisymmetric functions. We apply this result to a new framework of type B q-Schur positivity and to prove new equidistribution results for some sets of domino tableaux.

Soutenance de thèse de Julien Lavauzelle: «Codes à propriétés locales : constructions et applications à des protocoles cryptographiques»

Speaker: Julien Lavauzelle
Location: Amphi Sophie Germain, Bât. Alan Turing
Date: Ven. 30 nov. 2018, 15h00-16h30

Julien Lavauzelle, de l'équipe Grace, soutiendra sa thèse intitulée «Codes à propriétés locales : constructions et applications à des protocoles cryptographiques», le vendredi 30 novembre 2018 à 15h00 en salle Sophie Germain.

La soutenance aura lieu en anglais, devant le jury composé de :

  • Maura Paterson, Université Birbeck de Londres (rapporteure)
  • Christophe Ritzenthaler, Institut de recherche mathématique de Rennes (rapporteur)
  • Alain Couvreur, Inria Saclay (examinateur)
  • Camilla Hollanti, Université d'Aalto (examinatrice)
  • Gilles Zémor, Université de Bordeaux (examinateur)
  • Françoise Levy-dit-Vehel, ENSTA ParisTech (directrice de thèse)
  • Daniel Augot, Inria Saclay (co-encadrant)

Résumé: Les codes localement corrigibles ont été introduits dans le but d'extraire une partie de l'information contenue dans un mot de code bruité, en effectuant un nombre limité de requêtes à ses symboles, ce nombre étant appelé la localité du code. Ces dernières années ont vu la construction de trois familles de tels codes, dont la localité est sous-linéaire en la taille du message, et le rendement est arbitrairement grand. Ce régime de paramètres est particulièrement intéressant pour des considérations pratiques.

Dans cette thèse, nous donnons une rapide revue de littérature des codes localement corrigibles, avant d'en proposer un modèle combinatoire générique, à base de block designs. Nous définissons et étudions ensuite un analogue, dans le cas projectif, des relèvements affines de codes introduits par Guo, Kopparty et Sudan. Nous établissons par ailleurs plusieurs liens entre ces deux familles, pour finir par une analyse précise de la structure monomiale de ces codes dans le cas du relèvement plan.

Une deuxième partie de la thèse se focalise sur l'application de ces codes à deux protocoles cryptographiques. D'abord, nous proposons un protocole de récupération confidentielle d'information (private information retrieval, PIR) à partir de codes basés sur des designs transversaux, dont la taille des blocs s'apparente à la localité d'un code localement corrigible. Les protocoles ainsi construits ont l'avantage de n'exiger aucun calcul pour les serveurs, et de présenter une faible redondance de stockage ainsi qu'une complexité de communication modérée. Ensuite, nous donnons une construction générique de preuve de récupérabilité (proof of retrievability, PoR) à base de codes admettant une riche structure d'équations de parité à petit poids. Nous en donnons finalement une analyse de sécurité fine ainsi que plusieurs instanciations fondées sur des codes à propriétés locales.

Exposé par Wenjie Fang:«La transformation zeta steep-bounce dans le Cataland parabolique»

Speaker: Wenjie Fang (Univ. Graz)
Location: Salle Philippe Flajolet, Bât. Alan Turing
Date: Mer. 28 nov. 2018, 11h00-12h00

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 11h dans la salle Philippe Flajolet du LIX. Nous aurons le plaisir d'écouter Wenjie Fang (Univ. Graz) nous donner un exposé sur «La transformation zeta steep-bounce dans le Cataland parabolique». 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é: Etant un objet classique, le treillis de Tamari a beaucoup de généralisations, y compris les treillis ν-Tamari et les treillis de Tamari paraboliques. Dans cet article, ces deux treillis sont unifiés de manière bijective. D'abord nous prouvons que les treillis de Tamari paraboliques sont isomorphes aux treillis de ν-Tamari avec ν des chemins de rebond. Puis nous introduisons un nouvel objet dit ``arbre colorié à gauche'', et montrons qu'il donne un pont bijectif entre divers objets de Catalan paraboliques et certaines paires emboîtées de chemins de Dyck. En conséquence, nous prouvons la conjecture de steep-bounce par une généralisation de la fameuse transformation zeta dans la combinatoire de q,t-Catalan. C'est une collaboration en cours avec Cesar Ceballos et Henri Mühle.

Séminaire par Marie Kerjean: «Towards a type theory for differential equations»

Speaker: Marie Kerjean
Location: Salle Grace Hopper
Date: Wed, 28 Nov 2018, 10:30-12:00

Pour le prochain séminaire de l'équipe Cosynus, nous aurons le plaisir d'accueillir Marie Kerjean qui nous parlera de liens entre logique et équations différentielles.

Résumé: Linear Logic (LL) is a resource-aware refinement of intuitionnistic and classical logic, introduced after a study of denotational models of lambda-calculus. Differential Linear Logic (DiLL) spawned from denotational models LL based on vector spaces. While LL enriches logic with tools from algebra, DiLL transports those of differential calculus.

In this talk I will explain how we can refine DiLL into a system which solves linear partial differential equations with constant coefficients. This is done via a semantics study of DiLL, with a focus on smooth and classical models, in which the exponential is interpreted as a space of distributions. From this model, we can then understand exponentials as spaces of solutions to differential equations.

Information to newcomers

Location: *Sophie Germain* amphitheater.
Date: Wed, 28 Nov 2018, 14:00-16:00

Information afternoon for PhD students and postdocs who recently arrived in the Turing Building.

  • Welcome by M. Regnier (Director of LIX)
  • presentation of [referent]s for PhD students at LIX (M. Albenque and A. Couvreur)
  • Miscellaneous information on LIX and the Turing Building and the access to the network

It will be followed by a welcome drink in the atrium.

Bioinfo LIX/LRI joint seminar: Talks by Cédric Chauve and Nelle Varoquaux

Speaker: Cédric Chauve and Nelle Varoquaux
Location: Salle Flajolet, LIX
Date: Thu, 22 Nov 2018, 14:00-16:30

We are pleased to welcome Cédric Chauve (Simon Fraser university) and Nelle Varoquaux (UC Berkeley) next Thursday 22/11, 14h00, at LIX (building Alan Turing, 1 Rue Honoré d'Estienne d'Orves, 91120 Palaiseau) room Philippe Flajolet.

14h00 - Cédric Chauve (Simon Fraser university)

Title: On the Median and Small Parsimony problems in some genome rearrangement models.

Abstract: The main goal of genome rearrangement problems is to compute evolutionary scenarios that can explain the order of genes observed in extant genomes. This naturally leads to questions about the order of genes in ancestral genomes, often of extinct species. If a species phylogeny is given, this problem is known as the Small Parsimony Problem, and in its simplest form, where a single ancestral genome is considered, the Median Problem. Over the last 25+ years, there has been an extremely active research community focusing on these problems. In this talk, I will first review briefly some important results in the field, from initial intractability results to surprising tractability results, and then present some more recent results on (1) how to count or sample optimal solutions to these problems, and (2) how to handle gene duplication. The talk will be relatively free of technical details and will focus on algorithmic questions, leaving aside applications to the described algorithms.

15h10 - Nelle Varoquaux (UC Berkeley)

Tiltle: Studying the three-dimensional structure of DNA from Hi-C data

Abstract: Recent technological advances allow the measurement, in a single Hi-C experiment, of the frequencies of physical contacts among pairs of genomic loci at a genome-wide scale. The next challenge is to infer, from the resulting DNA-DNA contact maps, accurate three dimensional models of how chromosomes fold and fit into the nucleus. I will present a statistical method we developed for inferring genome-wide three-dimensional structure from Hi-C data, based on well-grounded statistical modeling of count data. I will then discuss how these models helped us better understand the links between gene expression and 3D structure of the malaria parasite P. falciparum. Last, I will briefly present how Hi-C data, initially developed to probe the 3D architecture of chromosome can help us annotate the genome. Specifically, I will show how we can identify precisely centromere positions in yeasts using Hi-C count maps.

Prochain séminaire "blocksem" jeudi 22 novembre : Juan Garay et Yannick Seurin

Speaker: Juan Garay et Yannick Seurin
Location: Salle Gilles Kahn, Bât. Alan Turing
Date: Jeu. 22 nov. 2018, 10h30-15h00

Les prochains exposés auront lieu le jeudi 22 novembre, bâtiment Turing, INRIA Saclay--Île-de-France et LIX en salle Gilles Kahn (rdc à droite).

Attention, l'inscription des extérieurs est obligatoire auprès de Maria-Agustina Ronco (donner nom, fonction et affiliation professionnelle).

10:30: Yannick Seurin. More Schnorr Tricks for Bitcoin.

12:-00-13:30: Repas (snack) ensemble dans le hall du bâtiment. Si vous n'avez pas de badge de restauration, signalez vous auprès de maria-agustina.ronco@inria.fr, nous prendrons gratuitement votre repas en charge.

13:30: Juan Garay, Texas A&M university. Foundational Aspects of Blockchain Protocols.

Le séminaire blocksem a une page web maintenue ici: http://www.lix.polytechnique.fr/blocksem/

Exposé par Pierre-Louis Giscard: «Une série pour la constante connective du réseau carré»

Speaker: Pierre-Louis Giscard
Location: Salle Philippe Flajolet, LIX
Date: Wed, 21 Nov 2018, 11:00-12:00

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 11h dans la salle Philippe Flajolet du LIX. Nous aurons le plaisir d'écouter Pierre-Louis Giscard (LMPA, Université du littoral Côte d'Opale) nous donner un exposé sur "Une série pour la constante connective du réseau carré". 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é: Nous montrerons comment, à l’aide d’un crible de la théorie des nombres, il est possible d’obtenir une série convergeant vers la constante connective μ dictant la croissance asymptotique du nombre de polygones auto-évitants d'un réseau régulier. Nous détaillerons la mise en oeuvre théorique et pratique du crible, notamment la nécessité de le faire fonctionner sur la densité des empilements de cycles d’un graphe plutôt que leur nombre. Ces considérations nous conduirons à mieux comprendre le terme dominant et les termes d’erreurs du crible, nous permettant finalement de calculer les 4 et 5 premiers ordres de la série donnant μ à 0.2% puis 0.06% près sur le réseau carré. Enfin, nous verrons ce qu’il reste à faire pour trouver la correction polynomiale sur le nombre de polygônes auto-évitants, qui nous échappe encore.