Laboratoire d'informatique de l'École polytechnique

News

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)

Séminaire par Véronique Bazier-Matte : «Conjecture d'unistructuralité des algèbres amassées»

Speaker: Véronique Bazier-Matte (LaCIM, UQAM)
Location: Salle Philippe Flajolet du LIX
Date: Mer. 18 avr. 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 Véronique Bazier-Matte (LaCIM, UQAM) nous parler de «Conjecture d'unistructuralité des algèbres amassées»

Resumé: En 2014, Assem, Schiffler et Shramchenko ont émis comme conjecture que toute algèbre amassée est unistructurelle, c'est-à-dire que l'ensemble des variables amassées détermine uniquement la structure d'algèbre amassée. Cette conjecture a été prouvée pour les algèbres de type fini, de rang 2 ou de type A-tilde. Dans cet exposé, nous exposerons quelques définitions et propriétés de base des algèbres amassées et nous expliquerons le concept d'unistructuralité des algèbres amassées. Puis, nous esquisserons la preuve pour certains cas où la conjecture est vérifiée. Pour ce faire, nous utiliserons les triangulations de surface et l'indépendance algébrique des amas.

Prochain séminaire BlockSem: Bruno Biais

Location: Salle Gilles Kahn, bâtiment Turin
Date: Jeu. 5 avr. 2018, 11h00-16h00

Pour la prochaine séance, il n’est prévu qu’un seul exposé: Bruno Biais nous parlera de «The blockchain folk theorem». En début d’après-midi, nous avons prévu une réunion informelle pour discuter d’orientations possibles/souhaitables pour BlockSem (e.g., nouveaux sujets, autres formes des interventions, fréquence, …).

Toutes les informations sont sur la page du séminaire.

Journées Nationales Informatique Mathématique

Location: École polytechnique, Palaiseau, France
Date: Mar. 3 avr. 2018, 14h00 - Ven. 6 avr. 2018, 16h00

Le LIX organise cette année sur le campus de l'X les Journées Nationales de l'Informatique Mathématique (JNIM'2018), événement phare du GdR Informatique Mathématique:

https://jnim2018.sciencesconf.org/

Nous aurons d'ailleurs le plaisir d'entendre, entre autres exposés donnés lors de ces journées, ceux de Marie-Paule Cani (Stream) et de Catuscia Palamidessi (Comète), ainsi que des anciens du LIX/DIX, Assia Mahboubi et Philippe Jacquet.

Nous vous attendons donc nombreux à cet événement, qui se conclura par une journée en hommage à Maurice Nivat.

La participation est gratuite, mais l'inscription est obligatoire : https://jnim2018.sciencesconf.org/registration

Inscrivez-vous !

Contacts: Stéphane Graham-Lengrand et Grégoire Lecerf

Exposé par Bérénice Delcroix-Oger: «Théorème de rigidité et fonctions de Parking»

Speaker: Bérénice Delcroix-Oger
Location: salle Philippe Flajolet, bât. Alan Turing
Date: Mer. 21 mars. 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 Bérénice Delcroix-Oger (IRIF) nous parler de «Théorème de rigidité et fonctions de Parking».

Résumé: Une question classique, mais difficile, de combinatoire algébrique est de savoir si une algèbre d'un type donné est libre sur l'ensemble de ses générateurs. Après avoir introduit tous les prérequis, j'expliquerai en quoi les théorèmes de rigidité pour les opérades, introduits en 2008 par Loday et récemment étendus, permettent d'apporter une réponse à ce genre de problème, notamment en ce qui concerne les algèbres des fonctions de Parking et des surjections. Ce travail a été fait en collaboration avec Emily Burgunder.

Sémin'Ouvert : « Algorithmes disons rapides pour factoriser les polynômes » par Grégoire Lecerf (LIX, équipe MAX)

Speaker: Grégoire Lecerf
Location: amphi. Germain (bât. Turing)
Date: Jeu. 15 mars. 2018, 14h30-15h30

Nous commencerons cet exposé par un aperçu des problèmes classiques de calculabilité et complexité liés à la factorisation des polynômes à une ou plusieurs variables. Nous expliquerons ensuite comment les différents sous-problèmes s'organisent habituellement selon les types de factorisation, les coefficients, et le nombre de variables. Enfin, nous montrerons comment fonctionnent quelques algorithmes récents.

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 !