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 laxiome du choix dépendant, qui peut être vu comme une adaptation de la preuve constructive de laxiome du choix en théorie des types de Martin-Löf ou une internalisation dans un système de preuve de lapproche 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. |
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 dextraction 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 dexpressivité pour composer différentes types de contraintes. L'utilisation de la PLNE pour la modélisation de tâches doptimisation 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 lextraction d'ensembles de motifs, je vais illustrer linté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 lapprentissage 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 lapprentissage sous contraintes des machines à vecteurs de support. Cette technique a été expérimentée sur loptimisation 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 savérer très lourd en temps de calcul lors de la phase dapprentissage. On propose une implémentation parallèle de lalgorithme 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é quon peut réduire significativement le temps dexécution ainsi que le nombre dattributs 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. |
|
|