2018


Retour à la vue des calendrier
Jeudi 5 Avril
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Apports de la Programmation Linéaire en Nombres Entiers pour la modélisation et l'extraction d'ensembles de motifs
Description: Abdelkader Ouali Un problème récurrent en extraction de motifs est la sélection de motifs pertinents parmi le grand ensemble de motifs découverts. Pour réduire le nombre de motifs extraits et donc de faciliter l'analyse du résultat de la fouille est l'extraction de motifs de plus haut niveau reposant sur des caractéristiques qui impliquent plusieurs motifs locaux. Ces motifs sont appelés ensembles de motifs ou pattern sets. Extraire le meilleur ensemble de motifs relativement à une mesure donnée permet de mieux cibler le processus d’extraction vers les meilleurs motifs mais rend la tâche plus ardue, notamment en raison de la taille importante de l'espace de recherche et le manque de techniques d'élagage efficaces pour ce type de problèmes. La plupart des approches existantes (souvent heuristiques) sacrifient la preuve d'optimalité au détriment de solutions approchées. Toutefois, la qualité de solutions obtenues par ces approches reste très variable.

La PLNE (Programmation Linéaire en Nombres Entiers) est un au cadre générique qui procure un haut niveau de flexibilité et d’expressivité pour composer différentes types de contraintes. L'utilisation de la PLNE pour la modélisation de tâches d’optimisation en fouille de données est un domaine qui a été très peu exploré. C'est dans ce cadre que s'inscrivaient mes travaux de thèse.

Dans cet exposé, je vais montrer comment la PLNE peut être utilisée pour modéliser différentes contraintes portant sur des ensembles de motifs. Outre le cadre général de l’extraction d'ensembles de motifs, je vais illustrer l’intérêt de mon approche sur deux problèmes bien connus en fouille de données : le clustering conceptuel et le problème de pavage (tiling). Enfin, je présenterai quelques résultats récents sur l'utilisation des moyennes ordonnées pondérées (communément appelées OWA pour Ordered Weighted) afin de trouver un équilibre optimal sur la taille des clusters du clustering conceptuel.
Vendredi 6 Avril
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Session-based concurrency, reactively
Description: Mauricio Cano This talk concerns formal models for the analysis of communication/centric software systems that feature declarative and reactive behaviors. We focus on session-based concurrency, the interaction model induced by session types, which uses (variants of) the pi-calculus as specification languages. While well-established, such process models are not expressive enough to specify declarative and reactive behaviors common in emerging communication-centric software systems.

Here we propose the synchronous reactive programming paradigm (SRP) as a uniform foundation for session-based concurrency. We present correct encodings of session-based calculi into ReactiveML, a synchronous reactive programming language. Our encodings bridge the gap between process specifications and concurrent programs in which session-based concurrency seamlessly coexists with declarative, reactive, timed, and contextual behaviors.
Mardi 10 Avril
Heure: 10:30 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: CIP : Equations différetielles non commutatives (préparation)
Description: Gérard DUCHAMP
Mercredi 18 Avril
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Apprentissage et génération de représentations optimisées de données complexes
Description: Abdelkader Benyettou On propose une approche mimétique pour l’apprentissage et la génération de représentations
optimisées de données complexes à travers la sélection et la pondération simultanée des attributs
basée sur une hybridation entre une approche évolutionnaire et l’apprentissage sous contraintes des
machines à vecteurs de support. Cette technique a été expérimentée sur l’optimisation de la
classification des documents web ainsi que des images aériennes. Cependant, les représentations
usuelles des données complexes engendrent des matrices de très grandes dimensionnalités dont le
traitement par une approche mimétique peut s’avérer très lourd en temps de calcul lors de la phase
d’apprentissage. On propose une implémentation parallèle de l’algorithme proposé basée sur les
modèles d’îlots afin de palier à ce problème. Nos expériences sur plusieurs benchmarks : Reuters-
21578, 7Sectors, Webkb et UCMerced LandUse ont montré qu’on peut réduire significativement le
temps d’exécution ainsi que le nombre d’attributs avec une nette amélioration des performances en
classification.
Mardi 24 Avril
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: CIP : Théorie de Picard-Vessiot et équations différentielles non commutatives
Description: Hoang Ngoc Minh Attention : Horaire décalé à 11h00 vu les difficultés de transport.
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Facteurs cyclotomiques des polynômes de Serre
Description: Florian Luca https://lipn.fr/~cb/Seminaires/resume.php?L=1165
Mercredi 2 Mai
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Discrete convexity and applications to combinatorics and optimization
Description: Gleb Koshevoy I will explain theory convexity for lattices, free Abelian groups without torsion. I will show that a famous class of polytopes, polymatroids of combinatorial optimization, is related to one of classes of discrete convexity. Several instances of discretely convex functions related to combinatorics of Young tableaux will be demonstrated.
Vendredi 11 Mai
Heure: 13:30 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: complexité algébrique III
Description: Paulin
Lundi 14 Mai
Heure: 14:00 - 15:30
Lieu: Salle B407, bâtiment B, Université de Villetaneuse
Résumé: Immerman-Szelepcsenyi
Description: Damiano
Mardi 15 Mai
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Phylogenetic trees modeled by increasing Schröder trees
Description: Mehdi Naima In biology a phylogenetic tree is a classical tool to represent the evolutionary relationship among
species. Our main frustration against the classical combinatorial models is related to the chrono-
logical aspect that seems not considered by the models. E. g. the Schröder trees do not take into
account the time evolution. We develop in this paper a model for phylogenetic trees satisfying
in priority two constraints: (1) to take into account the chronological evolution and (2) to be
efficient to simulate. Our model is based on some increasingly labeling of Schröder trees.
Heure: 12:00 - 13:30
Lieu: Salle A303, bâtiment A, Université de Villetaneuse
Résumé: logique catégorique I
Description: Damiano
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Strong and Cheap SDP and SOCP Hierarchies for Polynomi al Optimization
Description: Bissan Ghaddar In this talk, we propose alternative SDP and SOCP approximation hierarchies to obtain global bounds for general polynomial optimization problems (POP), by using SOS, and SDSOS polynomials to strengthen existing hierarchies for POPs. Specifically, we show that the resulting approximations are substantially more effective in finding solutions of certain POPs for which the more common hierarchies of SDP relaxations are known to perform poorly. Numerical results based on the proposed hierarchies are presented on non-convex instances form the literature as well as on instances from the GLOBAL Library.
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Hom-idempotent graphs, normal Cayley graphs and stable Kneser graphs
Description: Mario Valencia Pabon Dans cet exposé, on parlera de la notion de hom-idempotence dans l'ensemble de graphes : un graphe G est dit hom-idempotent s'il existe un homomorphisme entre le graphe produit cartésien G*G et G lui-même. Cette notion est fortement liée à une classe particulière de graphes de Cayley qu'on appelle les graphes de Cayley normaux. On montrera que les graphes de Kneser K(n,k) ne sont pas hom-idempotents. On montrera aussi que les graphes s-stables de Kneser K(n,k)_s ne sont pas hom-idempotents si s=2 mais, pour n=sk+1, K(n,k)_s est hom-idempotent. Finalement, on appliquera la notion de hom-idempotence à la k-tuple coloration de graphes : une k-tuple coloration de graphes consiste en affecter à chaque sommet un k-ensemble de couleurs de sorte que sommets adjacents reçoivent k-ensembles disjoints. On montrera que la différence entre le nombre chromatique du graphe produit cartésien de graphes de Kneser K(n,k)*K(n,k) et le nombre chromatique d'une 2-tuple coloration du même graphe K(n,k)*K(n,k) n'est pas bornée.
Mercredi 23 Mai
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Facteurs premiers de nombres remarquables
Description: Florian Luca Soit une suite de nombres entiers et considérons le produit des n premiers termes. Combien ce produit a-t-il de facteurs premiers ? Quel est le plus grand ? Nous présenterons différents résultats concernant des suites célèbres : les nombres de Fermat, de Fibonacci, ...
Heure: 15:00 - 16:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin Packing Problems
Description: Roberto Baldacci In this work, a new branch-and-price-and-cut algorithm is proposed to solve the one-dimensional bin packing problem (1D-BPP). The 1D-BPP is one of the most fundamental problems in combinatorial optimization and has been extensively studied for decades. Recently, Delorme et al. (2016) proposed 500 new test instances for the 1D-BPP; the best exact algorithm proposed in the literature can optimally solve 167 of these new instances, with a time limit of one hour imposed to each execution of the algorithm.
The exact algorithm proposed in this paper is based on the classical set-partitioning model for the 1D-BPP and the subset-row inequalities proposed by Jepsen et al. (2008). We describe an ad-hoc label-setting algorithm to solve the pricing problem, dominance and fathoming rules to speedup its computation and a new primal heuristic. The exact algorithm can easily handle some practical constraints, like the incompatibility between the items, and therefore we also apply it to solve the 1D-BPP with conflicts (1D-BPPC).
The proposed method is tested on a large family of 1D-BPP and 1D-BPPC classes of instances. For the 1D-BPP, the proposed method can optimally solve 237 instances of the new set of difficult instances; the largest instance involves 1003 items and bins of capacity 80,000. For the 1D-BPPC, the experiments show that the method is highly competitive with state-of-the-art methods, and successfully closed several open 1D-BPPC instances.
Vendredi 25 Mai
Heure: 14:00 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: type-two polynomial time and restricted lookahead
Description: Florian Steinberg
Mardi 29 Mai
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: (CIP) Discussion on graph rewriting systems (with examples and equations)
Description: Nicolas Behr Séminaire annulé à cause de difficultés de transport. Le séminaire de 14h00
est maintenu.
Heure: 14:00 - 16:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatorics of chemical reaction systems
Description: Nicolas Behr Reporting on recent work with G.H.E. Duchamp and K.A. Penson (arXiv:1712.06575), I plan to present a formulation of chemical reaction systems in the so-called stochastic mechanics formalism. This approach allows to uncover some deep relationships between the combinatorial techniques of boson normal-ordering and the dynamics of chemical reaction networks: each semi-linear reaction type induces an evolution within a space of probability distributions that can be computed explicitly via our techniques. For the interesting remaining types of reactions, some results involving systems of Sobolev-Jacobi orthogonal polynomials will be presented.
Jeudi 31 Mai
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Graphes dynamiques - Modélisation et Clustering
Description: Tabea Rebafka To model recurrent interaction events we propose a new dynamic random graph model : an extension of the stochastic block model in continuous time, where every individual (node) belongs to a latent group and interactions (edges) between two individuals are modelled using inhomogeneous Poisson processes. We develop a semiparametric variational expectation-maximization algorithm to estimate model parameters and to perform a clustering of the nodes. We illustrate the performance of our method on real datasets.
Mardi 5 Juin
Heure: 10:30 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Théorie de la complexité et géométrie des orbites du déterminant et du permanent
Description: Christophe Tollu Après un rappel sur les circuits arithmétiques et le problème de Valiant (VP vs VNP), je présenterai quelques résultats récents sur la "complexité déterminantale" du permanent, puis montrerai comment la version purement algébrique du problème VP vs VNP se prête à une reformulation en termes de géométrie des orbites du déterminant et du permanent (pour l'action d'un groupe algébrique sur les polynômes homogènes). Plusieurs ingrédients de base du programme de théorie géométrique de la complexité de Mulmuley et Sohoni seront présentés au cours de l'exposé bien que celui-ci ne soit pas "A crash course on Geometric Complexity Theory".
Jeudi 7 Juin
Heure: 11:30 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Coends and proof equivalence in MLL2
Description: Paolo Pistone > Proof nets provide permutation-independent representations of proofs and are used to investigate coherence problems for monoidal categories. We investigate a coherence problem concerning Second Order Multiplicative Linear Logic MLL2, that is, the one of characterizing the equivalence over proofs generated by the interpretation of quantifiers by means of ends and coends. This equivalence is naturally induced by the usual second order translation of multiplicative units and connectives and is related to the investigations on the parametric models of System F.
> By adapting the "rewiring approach" used in the proof net characterization of the free *-autonomous category, we provide a compact representation of proof nets for a fragment of MLL2 related to the Yoneda isomorphism. We prove that the equivalence generated by coends over proofs in this fragment is fully characterized by the rewiring equivalence over proof nets.
Mercredi 13 Juin
Heure: 14:00 - 15:00
Lieu: TBA (Institut Galilée)
Résumé: Network Interdiction
Description: Joe Naoum-Sawaya Network interdiction is a class of leader-follower optimization problem that seeks to identify network components to disrupt and inflict a maximum damage to a network. The objective of such models is to study the structural connectivity of the network in order to identify vulnerabilities. The application areas are diverse and include energy, telecommunication, and supply chain networks among others. This talk will review two particular variations of network interdiction: connectivity disruption and flow disruption. The connectivity disruption model identifies the nodes in a network whose disruption minimizes the maximum number of connected node pairs. The flow disruption model identifies the edges whose disruption minimizes the maximum flow between sources and destinations. We will present optimization models as well as solution approaches. We will particularly focus on the cases where uncertainty is present in the edge weights and propose customized solution approaches based on robust optimization, cutting planes, and Benders decomposition. The proposed cutting planes and Benders decomposition exploit the structure of the underlying optimization model and allows the modeling and the solution of general classes of uncertainty sets.
Jeudi 14 Juin
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Deep Cooperative Reconstruction with Privacy Constraints
Description: Denis Maurel Nowadays, we can observe a multiplication of multi-view data in domains such as marketing, bank administration or even survey analysis. In this context, Machine Learning methods are used to analyze data from several heterogeneous sources (here called views) with the following problem: an individual described in some views might be missing in some other ones. This proliferation is accompanied by a global privacy awareness: one should never have access to data from all sources at once. To solve these problems, we propose a method called the Cooperative Reconstruction System (CRS) which aims at reconstructing missing individuals locally using information contained in external views without data transfer from a view to another.
Vendredi 15 Juin
Heure: 10:30 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
Description: Joanna Ochremiak The isomorphisms between two graphs can be described by the solutions of a system of polynomial inequalities and equations. We analyse the relative power of different proof systems which can be used to certify that a system corresponding to a pair of non-isomorphic graphs has no solution. Our results complete a full cycle of implications to show that, for the graph isomorphism problem, the Sherali-Adams, Polynomial Calculus and Sums-of-Squares proof systems are equally powerful, up to a constant loss in the degree. We prove this statement purely about the relative strength of proof systems through an excursion into the descriptive complexity of the ellipsoid method and bounded-variable infinitary logics. This is joint work with Albert Atserias.
Jeudi 21 Juin
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Proposition et consommation de contenus sur le web : le problème de la diversité.
Description: Lionel Tabourier La question de la diversité des contenus proposés et consommés sur le web apparaît tôt dans la littérature de recherche d'information. Pourtant, ce n'est que récemment que celle-ci a évolué vers un débat de société, parce qu'un nombre croissant d'utilisateurs des moteurs de recherche ou des plateformes de recommandation sont confontés à leurs effets secondaires néfastes.

Un des plus notables est l'enfermement dans des bulles d'information, c'est-à-dire l'exposition à des contenus de moins en moins divers, correspondant à un environnement culturel restreint. L'objet du projet ANR Algodiv (http://algodiv.huma-num.fr/) est d'étudier comment le concept de diversité est traduit et mis en oeuvre par les algorithmes du web. Dans cet exposé, je présenterai deux aspects de cette question, qui sont des chantiers de travail actifs du projet.

D'abord, nous examinons l'effet des algorithmes de recommandation sur la diversité proposée aux utilisateurs. Moyennant une définition adéquate de la notion de diversité sur une plateforme de recommandation, nous cherchons à "auditer" les archétypes de recommandation, c'est-à-dire à mesurer la tendance d'une méthode à enfermer l'utilisateur à plus ou moins long terme.

D'autre part, nous étudions les caractéristiques des pratiques de navigation des utilisateurs sur l'exemple de la navigation sur le site Melty (https://www.melty.fr/). Nous examinons à quel point ceux-ci tendent à consommer des contenus variés ou non en fonction de ce qui leur est proposé, de la période, du moyen d'accéder à l'information, etc.
Lundi 25 Juin
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: The Arabic Ontology and Modernization of Lexical Semantic Resources
Description: Mustafa Jarrar The importance of lexical-semantic resources (linguistic ontologies, wordnets, thesauri, and dictionaries) is increasing in many modern application scenarios, such as multilingual big data, data governance, information retrieval, NLP, social networks, and others. In this talk we will present our experience in digitizing 150 multilingual lexicons and present the Arabic Ontology, which is a formal Arabic Wordnet with ontologically-clean content. We will also discuss how this content is ontologically we ll-founded and benchmarked to scientific advances rather than to speakers’ nai?ve beliefs as wordnets typically do, in addition to top levels and other ontology engineering challenges and mappings to other ontologies.
Mercredi 27 Juin
Heure: 14:00 - 15:00
Lieu: Salle Darwin, institut galilée
Résumé: Research Efforts at the Computational Approaches to Modeling Language Lab.
Description: Nizar Habash TBA
Jeudi 28 Juin
Heure: 14:00 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Hyperparameter Optimization for Neural Networks
Description: Razvan Andonie We introduce a dynamic early stopping condition for Random Search optimization algorithms. We test our algorithm for SVM hyperparameter optimization for classification tasks, on six commonly used datasets. According to the experimental results, we reduce significantly the number of trials used. Since each trial requires a re-training of the SVM model, our method accelerates the RS optimization. The code runs on a multi-core system and we analyze the achieved scalability for an increasing number of cores.