Laboratoire d'informatique de l'École polytechnique

News

Talk by Prof. Prashant Shenoy: «Designing Systems and Applications for Transient Computing»

Speaker: Prof. Prashant Shenoy
Location: Room Grace Hopper, LIX
Date: Tue, 24 Jul 2018, 14:00-15:00

On Tuesday we will have a talk by a visiting scholar, Prof. Prashant Shenoy, from the University of Massachusetts Amherst. Please find below the information of the talk and a shot bio of Prashant.

Abstract: Traditional distributed systems are built under the assumption that system resources will be available for use by applications unless there is a failure. Transient computing is a new phenomena that challenges this assumption by allowing system resources to become unavailable at any time. Transiency arises in many domains such as cloud computing--in the form of revocable spot servers--and in data centers that rely on variable electricity prices or intermittent renewable sources of energy Transiency is inherently different from fault tolerance since resources do not fail, rather they become temporarily unavailable, and traditional fault tolerance mechanisms are not suitable for handling transient resource unavailability.

In this talk, I will discuss how systems and applications need to be rethought to run on transient computing systems. I will first describe a system called Yank that uses a new bounded-time virtual machine migration mechanism to handle transiency at a system level while being transparent to applications. I will then discuss how modern distributed applications can be made transiency-aware and present a Spark-variant called Flint that we have developed to exploit transient cloud computing. I will end with open research questions in this area and directions for future work.

About the speaker: Prashant Shenoy is currently a Professor and Associate Dean in the College of Information and Computer Sciences at the University of Massachusetts Amherst. He received the B.Tech degree in Computer Science and Engineering from the Indian Institute of Technology, Bombay and the M.S and Ph.D degrees in Computer Science from the University of Texas, Austin. His research interests lie in distributed systems and networking, with a recent emphasis on cloud and green computing. He has been the recipient of several best paper awards at leading conferences, including a Sigmetrics Test of Time Award. He serves on editorial boards of the several journals and has served as the program chair of over a dozen ACM and IEEE conferences. He is a fellow of the IEEE and the AAAS and a distinguished member of the ACM.

Talk by Emilio Carrizos: «Sparseness in Classification and Regression. New steps.»

Speaker: Emilio Carrizosa (University of Seville, Spain, and Copenhagen Business School, Denmark)
Location: Room Henri Poincaré
Date: Fri, 20 Jul 2018, 09:00-10:00

Abstract: Classification and regression problems may involve data sets with (many) more variables than those which can be easily understood and interpreted. Sparsity is then a need. In this talk we will review several challenging problems in classification and regression, as well as the solutions Mathematical Optimisation provides to obtain sparsity.

Talk by Ruth Misener: «Lexicographic Optimisation for Rescheduling»

Speaker: Ruth Misener (Imperial College, UK)
Location: Room Henri Poincaré
Date: Fri, 20 Jul 2018, 10:00-11:00

Abstract: Responding reactively in scheduling environments subject to uncertainty may be modeled using reoptimization. Reoptimization begins by optimally solving an initial problem instance which is subsequently perturbed. The new objective is to update the initial optimal solution into a good solution for the new instance. We propose greedy algorithms and prove that they are efficient and tight for a variety of perturbations. In the case of job rejection or processing time reduction, reoptimization starting from an arbitrary optimal solution is not effective. But if our initial solution is lexicographic optimal, then we achieve a much better ratio. This result implies that reoptimization should be considered a two-step process where the phase of initial optimization has its own significance. For the initial phase, we propose a novel, branch-and-bound lexicographic optimization approach using vectorial bounds. Computational experiments with respect to the standard, weighted method validate our algorithm. This work is joint with Dr Dimitris Letsios.

Distinguished Paper award in IJCAI 2018

Giannis Nikolentzos, Michalis Vazirgianis and their co-authors have received the Distinguished Paper award (7 awards among the 710 accepted papers) in the major international AI conference IJCAI 2018 for their paper A Degeneracy Framework for Graph Similarity.

Workshop on Distributed Hybrid Systems

Speaker: Uli Fahrenberg
Location: Room Gilles Kahn
Date: Wed, 4 Jul 2018, 09:10-18:00

LIX hosts a workshop on distributed hybrid systems on wednesday, July 4th. The workshop will be in salle Gilles Kahn; we have 30 registered participants, so there should be plenty of room for extra spectators.

9:10 L. Fajstrup: Symmetries in the PV-model and of directed invariants

10:20 L. Jaulin: Distributed localization and control of underwater robots

13:30 E. Ledinot: Towards CPS certification reformation: call for effective foundations

14:20 A. Platzer: Logic of distributed hybrid systems

16:50 T. Dang: Invariance and stability verification of hybrid systems

See also http://dhs.gforge.inria.fr/#program

Joris van der Hoeven reçoit le prix Karp de l'Association of Symbolic Logic

Matthias Aschenbrenner, Lou van den Dries et Joris van der Hoeven ont reçu le prix Karp décerné par l'ASL (Association for Symbolic Logic), pour leur livre intitulé Asymptotic Differential Algebra and Model Theory of Transseries. Ce prix leur a été remis lors des rencontres annuelles de l'association.

Liens:

Exposé par Theo Douvropoulos: «Cyclic sieving for reduced reflection factorizations of the Coxeter element»

Speaker: Theo Douvropoulos
Location: Salle Philippe Flajolet
Date: Wed, 20 Jun 2018, 11:00-12:00

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi 20 juin à 11h dans la salle Philippe Flajolet du LIX. Nous aurons le plaisir d'écouter Theo Douvropoulos (IRIF, Univ. Paris 7) nous parler de «Cyclic sieving for reduced reflection factorizations of the Coxeter element». 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é: Given a factorization t1tn = c of some element c in a group, there are various natural cyclic operations we can apply on it; one of them is given by:


Ψ : (t1, ⋯, tn)→(c tn c−1, t1, ⋯, tn − 1).

A common question is then to enumerate factorizations with a certain degree of symmetry, that is, those for which Ψk is the identity, for a given k. In this talk we present the case of minimal length reflection factorizations of the Coxeter element c of a (well-generated, complex) reflection group W. The answer is a satisfying cyclic-sieving phenomenon; namely the enumeration is given by evaluating the following polynomial (in q) on a (nh/k)th root of unity:


$$X(q):=\prod_{i=1}^n\dfrac{[hi]_q}{[d_i]_q},\quad\quad\text{ where }[n]_q:=\dfrac{1-q^n}{1-q}.$$

Here, h is the Coxeter number (the order of c) and the di's are the fundamental invariants of W. The proof is based on David Bessis' pioneering work, which gave a geometric interpretation for such factorizations. We will only sketch the necessary background material and focus more on a topological braid-theoretic representation of cyclic operations such as Ψ. This is, in fact, the (combinatorial) heart of the argument.

Talk by Olivier Pietquin: «Guesswhat?! - Learning strategies for visually grounded dialogue»

Speaker: Olivier Pietquin
Location: Bât. Alan Turing
Date: Tue, 12 Jun 2018, 14:30-15:30

On Tuesday 12/06 at 14:30 we will have an interesting invited talk by Prof. Olivier Pietquin (Google Brain, Paris) on the topic: «Guesswhat?! - Learning strategies for visually grounded dialogue»

Abstract: In this talk we will present the Guesswhat?! game and the associated database. Guesswhat!? is a language-based game supported by an image in which one player selects an object in the image and the other has to discover that object by asking yes-no questions in natural language. A database of 150k dialogues have been collected and is freely available for research. Code for supervised learning baselines is also available. In addition, we will present recent work on Reinforcement Learning applied to that environment and some improvements brought to the supervised learning approach based on conditioning on language a feature-wise modulation of convnets.

Talk by Evangelos Kalogerakis: «Deep learning architectures for 3D shape analysis, synthesis, and animation»

Speaker: Evangelos Kalogerakis
Location: Room Gilles Kahn, Alan Turing building
Date: Tue, 5 Jun 2018, 15:30-16:30

Evangelos Kalogerakis (from University of Massachusetts at Amherst) will be visiting STREAM on Tuesday, the 5th of June, and will give a talk entitled: Deep learning architectures for 3D shape analysis, synthesis, and animation.

Abstract: The emergence of low-cost 3D acquisition devices, such as the Kinect, and the appearance of large-scale shape repositories, such as ShapeNet, are revolutionizing computer graphics, making 3D content ubiquitous. The need for algorithms that understand, intelligently process and animate 3D shapes is thus greater than ever. In this talk, I will present my latest research on deep learning architectures for 3D shape analysis, synthesis, and animation. Specifically I will describe deep architectures (ShapePFCN, SplatNet) that combine image-based and surface-based networks for 3D shape recognition and segmentation. In contrast to other deep learning approaches for 3D shape processing, the proposed architectures allow fast shape processing at high resolutions, are robust to input geometric representation artifacts, combine both image and shape datasets for training, and focus their representation power on the shape surface. Towards the end of the talk, I will also discuss recent advances on deep architectures that automate 3D shape animation, in particular facial animation, in an animator-friendly manner.

Séminaire par Krzysztof Ziemianski: «Directed paths on cubical complexes»

Speaker: Krzysztof Ziemianski
Location: Salle Marcel-Paul Schützenberger
Date: Lun. 28 mai. 2018, 15h00-16h00

Pour le prochain séminaire de l'équipe Cosynus, nous aurons le plaisir d'accueillir Krzysztof Ziemianski qui nous parlera de chemins dans des espaces topologiques dirigés.

Résumé: Let K be a semi-cubical set that satisfies certain mild conditions. I will present a construction of a CW-complex that is homotopy equivalent to the space of directed paths on the geometric realization of K from two fixed vertices of K. This construction satisfies certain minimality condition which makes it useful for direct calculations. Furthermore, this CW-complex carries a "permutahedral" structure - its cells can be identified with products of permutohedra and attaching maps are inclusions of faces. In the case when K is a Euclidean complex this model can be reduced further using Discrete Morse Theory. In some cases, for example if K is the space of states of a PV-program using only one resource, this leads to the optimal construction: the cells of the constructed CW-complex are in 1-1 correspondence with the generators of homology of the directed path space.

Séminaire par Jérémie Bettinelli: «Convergence of uniform noncrossing partitions toward the Brownian triangulation»

Speaker: Jérémie Bettinelli
Location: Salle Philippe Flajolet
Date: Mer. 23 mai. 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 Jérémie Bettinelli nous parler de Convergence of uniform noncrossing partitions toward the Brownian triangulation. Le résumé est disponible ci-dessous.

Abstract: We give a short proof that a uniform noncrossing partition of the regular n-gon weakly converges toward Aldous's Brownian triangulation of the disk, in the sense of the Hausdorff topology. This result was first obtained by Curien and Kortchemski, using a more complicated encoding. Thanks to a result of Marchal on strong convergence of Dyck paths toward the Brownian excursion, we furthermore give an algorithm that allows to recursively construct a sequence of uniform noncrossing partitions for which the previous convergence holds almost surely. In addition, we also treat the case of uniform noncrossing pair partitions of even-sided polygons.

Sémin'Ouvert : « Minimal Distance of Propositional Models » par Miki Hermann (équipe AlCo)

Speaker: Miki Hermann
Location: Salle G. Kahn
Date: Jeu. 17 mai. 2018, 14h30-15h30

We investigate the complexity of three optimization problems in Boolean propositional logic related to information theory: Given a conjunctive formula over a set of relations, find a satisfying assignment with minimal Hamming distance to a given assignment that satisfies the formula (Next Solution) or that does not need to satisfy it (Nearest Solution). The third problem asks for two satisfying assignments with a minimal Hamming distance among all such assignments (Min Solution Distance).

For all three problems we give complete classifications with respect to the relations admitted in the formula. We give polynomial time algorithms for several classes of constraint languages. For all other cases we prove hardness or completeness regarding APX, polyAPX, or equivalence to well-known hard optimization problems.

This is joint work with Mike Behrisch (TU Wien), Stefan Mengel (CRIL), et Gernot Salzer (TU Wien).

Exposé de Sanjay Ramassamy: «Extensions d'ordres cycliques partiels, boustrophédons et polytope

Speaker: Sanjay Ramassamy
Location: Salle Philippe Flajolet, LIX
Date: Mer. 16 mai. 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 Sanjay Ramassamy (UMPA, ENS Lyon) nous parler d' «Extensions d'ordres cycliques partiels, boustrophédons et polytopes». 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é: Tandis que l'énumeration des extensions linéaires des ensembles partiellement ordonnés a fait l'objet de nombreux travaux, son analogue cyclique (énumération des extensions à des ordres cycliques totaux d'un ordre cyclique partiel donné) a été fort peu étudié. Dans cet exposé, j'introduirai certaines classes d'ordres cycliques partiels pour lesquels ce problème d'énumération est tractable. Certains cas font appel à une version multidimensionnelle de la construction du boustrophédon, un triangle de nombres utilisé pour calculer les nombres zigzags d'Euler. J'expliquerai aussi le lien entre ces questions d'énumération d'extensions d'ordres cycliques partiels et le calcul du volume de certains polytopes.

Il s'agit d'un travail en partie en commun avec Arvind Ayyer (Indian Institute of Science) et Matthieu Josuat-Vergès (LIGM / CNRS)

Maks Ovsjanikov, lauréat de la médaille de bronze du CNRS

Maks Ovsjanikov, de l'équipe Stream, vient de se voir décerner la médaille de bronze du CNRS. Félicitations à lui !