2018


Retour à la vue des calendrier
Mardi 16 Janvier
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Chute de dimension pour les marches aléatoires sur les arbres aléatoires
Description: Pierre Rousselin Nous nous intéressons à différents modèles d'arbres aléatoires et aux marches aléatoires sur les sommets de tels arbres.Dans le cas où la marche aléatoire est transiente, la marche part presque sûrement vers l'infini en empruntant un rayon aléatoire.La loi de ce rayon est appelée la mesure harmonique sur le bord de l'arbre.Un phénomène de chute de dimension se produit : cette mesure harmonique est presque sûrement concentrée sur une partie petite (au sens de la dimension de Hausdorff) du bord de l'arbre.Autrement dit, les trajectoires de la marche aléatoires sont presque sûrement comprises dans un sous-arbre beaucoup plus fin que l'arbre original.Cette théorie a été initiée par Russel Lyons, Robin Pemantle et Yuval Peres dans les années 1990.Plus récemment, Nicolas Curien, Jean-François Le Gall, puis Shen Lin ont étudié ce phénomène sur un autre modèle d'arbres aléatoires.Nous rappellerons leurs résultats et discuteront des généralisations(https://arxiv.org/abs/1708.06965 et https://arxiv.org/abs/1711.07920) sur lesquelles nous avons travaillé.
Mardi 23 Janvier
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Uniform generation of infinite concurrent runs: the case of trace monoids
Description: Vincent Jugé
Lundi 29 Janvier
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Approches non supervisées pour l'extraction de relations sémantiques
Description: Kata Gabor Les approches actuellement utilisées pour l’extraction d’informations et
de connaissances s'appuient majoritairement à la classification
supervisée ou semi-supervisée. Elles exploitent des bases de
connaissances structurées qui fournissent un modèle des connaissances,
et le plus souvent également des données annotées par des humains. Or,
de telles ressources sont couteuses à produire en matière de temps et
d’expertise, et l'adaptation de domaine pose des difficultés.

Nous cherchons à mettre en oeuvre des méthodes d'extraction
d'informations qui minimisent les besoins en intervention humaine. Nous
proposons et comparons plusieurs approches à la tâche d'extraction non
supervisée de relations sémantiques à partir de corpus. Les approches
ont été évaluées sur un corpus de domaine de taille limité, ainsi que
sur un corpus et un jeu d'évaluation de vocabulaire générique. La
première approche utilise des word embeddings pour caractériser le sens
des concepts et pour calculer la similarité relationnelle entre
plusieurs paires de concepts. La deuxième approche utilise la fouille de
motifs séquentiels, combiné avec l'analyse sémantique, pour identifier
les contextes qui permettent de détecter les relations. Finalement, nous
proposons des pistes d'amélioration, en particulier en ce qui concerne
l'hybridisation des deux approches.
Mardi 30 Janvier
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Decomposition methods for quadratic programming
Description: Emiliano Traversi The purpose of this talk is to present two decomposition methods for quadratic problems. First, we propose a methodological analysis on a family of reformulations combining Dantzig-Wolfe decomposition and Quadratic Convex Reformulation principles for binary quadratic problems. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem. Secondly, we analyze a simplicial decomposition like algorithmic framework that handles convex quadratic programs in an effective way. In particular, we propose two tailored strategies for solving the master problem and we describe a few techniques for speeding up the solution of the pricing problem. We report extensive numerical experiments on both real-world and generic quadratic programs.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A panorama on real solutions of polynomial systems, illustrated via the RAGLib Maple package
Description: Mohab Safey El Din
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Aspects énumératifs et bijectifs des cartes combinatoires
Description: Wenjie Fang Les cartes combinatoires, étant un modèle riche, portent plusieurs aspects : algébrique, géométrique, bijective, ... Dans cet exposé, je présente un ensemble de résultats et de connexions dans le domaine de l'énumération des cartes, obtenus à travers des aspectsdifférents. Nous verrons comment utiliser les outils algébrique, comme caractères du groupe symétrique et équations fonctionnelles, à énumérer les cartes. Nous verrons aussi comment étudier les autres objets dans la combinatoire, ici les intervalles du treillis deTamari, à travers de l'aspect bijectif des cartes.
Heure: 16:30 - 18:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A unified framework for notions of algebraic theory
Description: Soichiro Fujii Universal algebra uniformly captures various algebraic structures, by expressing them as equational theories or (abstract) clones. The ubiquity of algebraic structures in mathematics has also given rise to several variants of universal algebra, such as symmetric and non-symmetric operads, clubs, and monads. In this talk, I will present a unified framework for these cousins of universal algebra, or notions of algebraic theory.

First I will explain how each notion of algebraic theory can be identified with a certain monoidal category, in such a way that theories correspond to monoids. Then I will introduce a categorical structure underlying the definition of models of theories. In specific examples, it often arises in the form of oplax action or enrichment. Finally I will uniformly characterize categories of models for various notions of algebraic theory, by a double-categorical universal property in the pseudo-double category of profunctors.
Vendredi 2 Février
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Probabilistic Rewriting
Description: Claudia Faggian We investigate how techniques from Rewrite Theory can help us to study calculi whose evaluation is both probabilistic and non-deterministic (think untyped probabilistic lambda-calculus, in which non-determinism arises from choosing between
different redexes). We are interested in relations between week and strong normalization, and whatever the result is unique. In particular, we characterize the properties “non-determinism is irrelevant” and “strategy A is always better than strategy B”.

As an application, it turns out that probabilistic lambda-calculus equipped
with weak call-by-value reduction has striking properties.
Vendredi 16 Février
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Des Preuves Syntactiques aux Preuves Combinatoires
Description: Matteo Acclavio Dans cet exposé nous allons étudier les preuves combinatoires de Hughes comme notion de identité de preuve pour la logique classique.
Nous montrons comment divers formalismes, notamment le caclulus des sequents, les tableaux analytiques et la résolution, peuvent être traduits en preuves combinatoires, et quelle notion d'identité ils appliquent.
(Joint work with Lutz Strassburger)
Mardi 20 Février
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Disques browniens
Description: Jérémie Bettinelli À l'instar du mouvement brownien qui apparaît comme limite d'échelle universelle de toute marche aléatoire raisonable, les disques browniens sont des espace métrique aléatoires qui apparaissent comme limite d'échelle universelle de modèles raisonables de cartes
aléatoire du disque. Ces objets généralisent la carte brownienne de Miermont et Le Gall obtenue en considérent des cartes aléatoire de la sphère.

Nous présenterons les disques browniens et en donneront quelques propriétés remarquables. Ce travail est en commun avec Grégory Miermont.
Mardi 6 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Two fast parallel GCD algorithms of many integers
Description: Sidi Mohamed Sedjelmaci
On montre que le calcul du PGCD de ???? integers de ????(????) bits peut se faire en parallèle en temps ????(???? / log ????) avec ????(????????^(1+????) ) processors, pour tout 2 ? ???? ? ????^(3/2) / log ????, c'est-à-dire que le temps de calcul en parallèle ne dépend pas dépend du nombre d'entiers m considéré dans cet intervalle.
Mardi 20 Mars
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: On the Interplay between Simple Mixed Integer Programs and Lot-Sizing
Description: Laurence A. Wolsey After introducing some of the most basic lot-sizing problems and their properties, we show how the study of tight MIP formulations for the convex hull of solutions of such problems has provided more general results for MIPs and vice versa. In particular we demonstrate the importance of compact extended formulations as well as the role of mixing sets, network dual MIPs and single node flow models.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: On lattice polytopes, convex matroid optimization, and degree sequences of hypergraphs
Description: Antoine Deza We introduce a family of polytopes, called primitive zonotopes, which can be seen as a generalization of the permutahedron of type Bd. We discuss connections to the largest diameter of lattice polytopes and to the computational complexity of multicriteria matroidoptimization. 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 computationallyprohibitive. Based on joint works with Asaf Levin (Technion), George Manoussakis (Paris Sud), Shmuel Onn (Technion).
Vendredi 23 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Gdt Complexité suite
Description: Paulin de Naurois Suite du premier gdt
Mardi 27 Mars
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatorial bases of KZn
Description: Gleb Koshevoy TBA (discussion)
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Complexity of the cluster deletion problem on cographs and subclasses of chordal graphs
Description: Mario Valencia Pabon We consider the following vertex-partition problem on graphs,
known as the CLUSTER DELETION (CD) problem: given a graph with real
nonnegative edge weights, partition the vertices into clusters (in this
case, cliques) to minimize the total weight of edges outside the
clusters. The decision version of this
optimization problem is known to be NP-complete even for unweighted
graphs and has been studied extensively. In this talk, I will focus on
the complexity of the decision CD problem for the family of chordal
graphs, showing that it is NP-complete for weighted split graphs,
weighted interval graphs and unweighted chordal graphs. We will also see
that the problem is NP-complete for weighted cographs. Some
polynomial-time solvable cases of the optimization problem will be
identified, in particular CD for unweighted cographs, split graphs,
unweighted proper interval graphs and weighted block graphs.

This is a joint work with Flavia Bonomo and Guillermo Duràn (University
of Buenos Aires).
Heure: 14:00 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Cluster relations among Schur functions and a positivity conjecture
Description: Gleb Koshevoy Cluster algebras, invented by Sergey Fomin and Andrei Zelevinsky around 2000,
are commutative algebras whose generators and relations are constructed in a recursive manner.
Due to cluster recursion we obtain Laurent polynomials in the initial variables, so-called Laurent
phenomenon of cluster algebras. The coordinate ring of base affine space C[N_-SL_n] plays an important role in representation theory and is endowed with a cluster algebra structure. We show that under specialization of minors to Schur functions, Laurent polynomials of this cluster algebra turn into 'homogeneous' sums of Schur function. A positivity conjecture says that these sums have positive coefficients. This conjecture is true for finite cluster subalgebras.
Vendredi 30 Mars
Heure: 11:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Un calcul des séquents avec des types dépendants pour l'arithmétique classique
Description: Etienne MIQUEY En 2012, Hugo Herbelin définit dPA?, un langage typé qui fournit, dans un cadre compatible avec la logique classique, un terme de preuve pour l’axiome du choix dépendant, qui peut être vu comme une adaptation de la preuve constructive de l’axiome du choix en théorie des types de Martin-Löf ou une internalisation dans un système de preuve de l’approche en réalisabilité de Berardi, Bezem et Coquand. Malheureusement ce calcul ne dispose pas d'une preuve de normalisation, la difficulté d'une telle preuve est liée à la présence simultanée de types dépendants (pour la partie constructive du choix), d'opérateurs de contrôle (pour la logique classique), d'objets co-inductifs (pour "encoder" les fonctions de type N ? A par des streams (a?,a?,...)) et d'évaluation paresseuse avec partage (pour ces objets co-inductifs).
Durant cet exposé, nous verrons comment définir une variante de dPA? en calcul des séquents dont on pourra prouver la correction. Au passage, on montrera la normalisation du call-by-need classique (présenté comme une extension du ?µµ?-calcul avec des environnements partagés) en utilisant notamment des techniques de réalisabilité à la Krivine ; et l'on développera un calcul des séquents classique avec types dépendants, dont la correction est prouvable à l'aide d'une traduction CPS tenant compte des dépendances.