2014


Retour à la vue des calendrier
Mardi 4 Mars
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Problème de placement orthogonal
Description: Petru Valicov Etant donné un conteneur rectangulaire C, on s'intéresse à
décider si un ensemble d'items rectangulaires peut être placé sans
chevauchement et sans dépassement des bords de C. Une contrainte
supplémentaire est prise en compte -- l'interdiction de rotation des
items. Ce problème est NP-complet et est un sous-problème du problème de
sac-à-dos orthogonal où à chaque item on associe un profit et on cherche
le sous-ensemble d'items réalisable de profit total maximum. Fekete et
Schepers ont introduit une caractérisation élégante des solutions du
problème de placement en utilisant les graphes d'intervalles. Nous
présentons une nouvelle caractérisation en utilisant des MPQ-arbres --
des structures de données qui encodent efficacement les graphes
d'intervalles. Un des principaux avantages de cette caractérisation est
un nombre plus restreint des solutions symétriques traitées lors de
l'exécution de l'algorithme. Nous finiront par présenter une comparaison
des résultats avec ceux de la littérature sur les jeux de données
connus. Travail effectué en collaboration avec C. Joncour et A. Pêcher.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Rationality of growth in the Heisenberg groups
Description: Moon Duchin I'll discuss the history of work on the question of how andwhether rationality of growth depends on generators. That is, for afinitely generated group, one can study the growth function (the number ofwords spellable in up to n letters) and its growth series, the associatedgenerating function. This growth series is itself a rational function whenthere is a recursive relationship among the values of the growth function. It is known that all virtually abelian groups and all hyperbolic groupshave rational growth in any generators, by work of Benson and Cannonrespectively. Work of Shapiro and of Stoll sheds some light on thesituation in nilpotent groups, but shows it to be more complicated-- evenfor the second Heisenberg group H_5, some generators give rational growthbut others do not. I'll describe work in progress with Shapiro givinggeometric arguments to establish rationality in all generators for theclassical Heisenberg group H_3.
Vendredi 7 Mars
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Lambda-calculus and the Invariance Thesis
Description: Beniamino Accattoli








reasonable λλλλsize
explosion problemλλimpasse usefulβi.e.
Mardi 11 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Convolution de Dirichlet et énumération de pyramides et espaliers
Description: Matthieu Deneufchâtel Nous étudions l'énumération de deux familles de polycubes, lespyramides et les espaliers, en lien avec une version multi-indexée de laconvolution de Dirichlet.
Vendredi 14 Mars
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: On type isomorphisms in simultaneous presence of sums and functions
Description: Danko Ilik We consider the problem of characterizing isomorphisms of types, or, equivalently, constructive cardinality of sets, in the simultaneous presence of disjoint unions, Cartesian products, and exponentials. Mostly relying on results about polynomials with exponentiation that have not been used in our context, we derive: that the usual finite axiomatization known as High-School Identities (HSI) is complete for a significant subclass of types; that it is decidable for that subclass when two types are isomorphic; that, for the whole of the set of types, a recursive extension of the axioms of HSI exists that is complete; and that, for the whole of the set of types, the question as to whether two types are isomorphic is decidable when base types are to be interpreted as finite sets. We also point out certain related open problems.
Mardi 18 Mars
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Quelques projets autour de méthodes de génération de colonnes et d'algorithmes mémétiques
Description: Daniel Porumbel Après une introduction générale, la première partie de cette communication présentera en lignes générales quelques travaux sur deux axes de recherche. 1.Bornes duales à base de méthodes de génération de colonnes Deux projets sont évoqués:  1.A. Génération de Colonnes à Base d'un (Sous-)Problème d'Intersection    De point de vue dual, la génération de colonnes fonctionne comme une méthode à     base de plans sécants (e.g., "Kelley's cutting plane") dans le polytope dual P.     Pour ajouter itérativement des contraintes duales (colonnes), la génération de    colonnes fait appel à un sous-problème de séparation sur P. On propose une     méthode qui permet d'optimiser P en faisant appel à un sous-problème d'inter-    section au lieu du sous-problème de séparation.  Ce sous-problème d'intersection    demande d'avancer sur la direction 0->r d'un "rayon" r jusqu'au moment où on     intersecte une facette de P. On génère une séquence de rayons r1, r2, ... qui    convergent vers 0->OPT(P) où P est la solution dual optimale. Des résultats seront    présentés pour quelques versions de Cutting-Stock et sur Arc-Routing 1.B. Méthodes d'agrégation duale    Pour réduire la taille du polytope dual P, nous avons groupé et agrégé les variables    duales en k groups. Cela permet d'obtenir un polytope agrégé Pk complètement     inclus dans P. On augment k itérativement, et ainsi, OPT(Pk) converge vers OPT(P).2. Bornes primales à l'aide d'algorithmes "Spacing Memetic"    Dans ce travail, nous proposons une méthode à base de distances entre solutions    candidates pour contrôler la diversité de la population d'un algorithme mémétique.    L'approche possède des similarités avec "MA|PM" (Memetic Algorithms with Population Management).      La deuxième partie présente plus en détail le projet 1.A. ci-dessus, suivi de différentesperspectives.
Vendredi 21 Mars
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Can Dialectica break bricks?
Description: Pierre-Marie Pédrot
The Dialectica translation is a logical transformation described by
Gödel in 1958, but designed in the 30's. At the end of the 80's, it was
given a categorical counterpart, which happened to be compatible with
the usual decomposition of intuitionistic logic into linear logic.
Still, it was lacking a true Curry-Howard interpretation.
We will fill this hole by presenting the computational content of
Dialectica by means of an untyped lambda-calculus translation. We will
show that this translation has a really simple explanation as soon as we
put our source term in the Krivine abstract machine, except for a
disturbing detail, seemingly deeply rooted in linear logic. We will also
show how our presentation can be naturally applied to a
dependently-typed system almost without adaptation, thus giving a
hindsight on how linear dependent types may be built (or not).
Mardi 25 Mars
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: The robust vehicle routing problem with time windows and travel time uncertainty
Description: Rosa Figueiredo This work addresses the robust vehicle routing problem with time windows. We are motivated by a problem
that arises in maritime transportation where delays are frequent and
should be taken into account. Our model only allows routes that are
feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a robust optimization problem. We propose two new formulations for the robust problem, each based on a different decomposition approach. The first formulation extends the well-known resource inequalities formulation by employing robust programming with recourse. The formulation is solved by a row-and-column generation algorithm. The second formulation generalizes a path inequalities formulation to the
uncertain context and is solved through a row generation algorithm. In
particular, we discuss efficient separation procedures. We compare the two formulations on maritime transportation instances.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Autour des automates cellulaires probabilistes
Description: Irène Marcovici Un automate cellulaire probabiliste (ACP) est une chaîne de Markov sur un espace symbolique. Le temps est discret, les cellules évoluent de manière synchrone, et le nouvel état de chaque cellule est choisi de manière aléatoire, indépendamment des autres cellules, selon une distribution déterminée par les états d'un nombre fini de cellules situées dans le voisinage.Je présenterai les résultats obtenus au cours de ma thèse sur deux "problèmes inverses" : le premier consiste à étudier les ACP ayant des mesures invariantes de forme produit de Bernoulli ; le second est le problème de la classification de la densité, qui consiste à trouver un AC(P) dont l'évolution permette de distinguer une configuration initiale sur l'alphabet binaire tirée selon une mesure de Bernoulli de paramètre inférieur ou supérieur à 1/2, et que nous avons résolu sur les grillesde dimension supérieure ou égale à 2 et sur les arbres.
Vendredi 28 Mars
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Interaction Graphs and Complexity
Description: Thomas Seiller We obtained, with C. Aubert, new characterizations of complexity classes
coNL and L using methods inspired from Girard's hyperfinite Geometry of
Interaction (GoI). These characterizations had some drawbacks, among which:
- it used complicated tools from operator theory;
- it was not related to the interpretation of logic in the Geometry of
Interaction construction;

This work revisits these previous results by using Interaction Graphs, a
combinatorial GoI construction developed during my thesis that
simplifies, unifies and generalizes Girard's GoI constructions. This
change of perspective allows for a number of improvements, namely:
- the obtention of simplified characterizations of the classes coNL and L;
- the obtention of new characterizations, e.g. Regular languages, NL;
- it relates the method to the reconstruction of logic in Interaction
Graphs (hence in GoI);
- it offers new ways to obtain characterizations of other classe.
Mardi 1 Avril
Heure: 14:15 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Sur la structure palindromique des mots
Description: Srecko Brlek En combinatoire des mots finis ou infinis, la nature des motifs qui apparaissent dans un mot donné sont une des nombreuses manières de déterminer sa complexité. Les calculs de diverses statistiques permettent de mettre en évidencecertaines relations qu'il vérifie.
Vendredi 4 Avril
Heure: 10:00 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: De la charactérisation des modèles de H*
Description: Flavien Breuvart Je donnerais une caractérisation (pour une large classe de model du
lambda calcul pur) des modèles qui sont pleinement adéquat pour la
normalisation de tête, càd dont la théorie est H*. Un K-model
extentionel D est pleinement adéquat sii il est hyperimmune, càd que
les comportements mal fondés ne sont pas capturées par aucun terme
récursif.
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A Core Quantitative Coeffect Calculus
Description: Aloïs Brunel Monadic notions of computation are well-established mechanisms used to express effects in pure functional languages. Less well-established is the notion of comonadic computation. However, recent works have shown the usefulness of comonads to structure context dependent computations. In this talk, we present a language, called lRPCF, inspired by a generalized interpretation of the exponential modality of bounded linear logic. In lRPCF exponential modalities carry a label--an element of a semiring--providing additional information on how a program uses its context. This additional information is used to express comonadic type analysis.
Mardi 8 Avril
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Split Cuts and Separable Underestimator for non-convex quadratic problems
Description: Emiliano Traversi In this work we investigate the computational potential of two tools
for solving non-convex quadratic problems: split inequalities and
separable underestimator.
Split inequalities were first introduced by Letchford and further
examined by Burer and Letchford. For small instances with
box-constraints, we show that the resulting dual bounds are very
tight.The gap can be further decreased by separating so-called
non-standard split inequalities, which we examine in the case of ternary variables.Separable
underestimator are used for solving constrained quadratic binary
programming. Dual bounds are computed by choosing appropriate
underestimators of the objective function that are separable but not
necessarily convex. We explain how to embed this approach into a
branch-and-bound algorithm and present experimental results for several
classes of combinatorial optimization problems, including the quadratic
shortest path problem, for which we provide the first exact approach
available in the literature.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Réunion des CS pour audition MdC et Prof
Jeudi 10 Avril
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Behavior driven design for tests and verification
Description: Ulrich Kühne In the course of an exploratory project on hardware and system design and verification, we are looking for new ways how to bridge the gap between early abstract models and later implementation phases. One possible approach is the adaptation of agile techniques to the hardware domain, enhanced by model checking techniques. While in the design of hardware systems, testing and verification are usually applied as a post-process, software developement is pushed towards agile techniques like Test Driven Development (TDD), where tests play a central role. Behavior driven development (BDD) extends TDD as a well established software development technique. Essentially, in both techniques testing and implementing is interleaved, with the test cases being written first. In BDD, test cases are written in natural language which enables the discussion with stakeholders and easy requirements tracking throughout the design. In this talk, I will present a BDD tool for the Verilog hardware design language, which extends BDD with formal techniques. From test cases, properties can be generalized, making the verification more reliable, without the need to manually specify temporal properties.
Vendredi 11 Avril
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Hypercoherence Spaces form a double-glued Category
Description: Hugh Steele Ehrhard's Hypercoherence Spaces proved a useful medium through which to
study strongly stable semantics. The category of hypercoherence spaces
(HypCoh) has also been shown to be the bedrock of one of the very few
fully complete models of unit-free multiplicative additive linear logic,
satisfying Joyal's softness condition. Much like in the category of
coherence spaces (Coh), an object of HypCoh is a set equipped with a
collection of its subsets, with morphisms being relations respecting
restrictions set by these `cliques'. However, unlike Coh, HypCoh has not
been formalised as a true double-glued category.

In this talk I show that HypCoh is indeed such a category (if you're
willing to bend the rules a little!). We also see how far the spirit of
the glueing construction may be generalised to produce categories with
similar properties.
Mardi 15 Avril
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Some algebraic structures on chip firing game
Description: Ha Duong Phan The chip firing game is a discrete dynamical model ongraphs which was first defined by D. Dhar (1990) and by A. Björner, L.Lovasz and W. Shor (1991). The model has various applications in manyfields of science such as physics, computer science, social science andmathematics. Recently, this model is used as a tool to study manyproperties of graphs and it was proved to be related to subjects of graphtheory, such as Laplacian matrix, Tutte polynomial, spanning tree orgraphic matroid, etc. In this talk, I will present some algebraicstructure raised on this model.
Samedi 26 Avril
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Unification and Logarithmic space
Description: Marc Bagnol I will present an algebraic characterization of the complexity
classes Logspace and NLogspace, using an algebra with a composition
law based on unification. This bridge between unification and
complexity classes is inspired from proof theory and more specifically
linear logic and Geometry of Interaction.
Mardi 29 Avril
Heure: 00:00 - 03:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: exposés ANR Magnum à P6: O. Bodini & A. Sportiello
Lundi 5 Mai
Heure: 14:15 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Entity-centric computing
Description: Aldo Gangemi Chez le web sémantique, l'intégration des connaissances extraites de textes et de données sous forme de graphes sémantiques à monde ouvert, avec l'identité des “ressources” (entités) dereferenceable (“ancrée") sur le web, offre un solution incomplète, mais très pratique pour étudier empiriquement des phénomènes sémantiques.
Mardi 6 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Sur les diamètres de certains graphes de flips
Description: Lionel Pournin Considérons une surface orientable S de genre g avec k>0bords. Plaçons un ensemble E de n points sur S de manière que chaquebord contienne au moins un de ces points. Le graphe des flips de E estle graphe G dont les sommets sont les triangulations de E et dont lesarêtes joignent deux triangulations qui peuvent être transforméesl'une en l'autre par un flip (cette opération consiste à échanger lesdiagonales d'un quadrilatère). Le graphe G est connexe. Si onconsidère les triangulations de E à homéomorphisme près, les sommetsde E étant marqués, le diamètre de ce graphe est borné.Lorsque S est un disque dont le bord contient tous les points de E, Gest le graphe de l'associaèdre de dimension n-3. Il a été montrérécemment que le diamètre de ce graphe est 2n-10 dès que n estsupérieur à 12. La preuve de ce résultat sera esquissée. Plusieursautres résultats sur le diamètre de G seront ensuite donnés etdiscutés dans le cas où S n'est pas un disque.
Lundi 12 Mai
Heure: 14:15 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Hybridation TAL / KE pour l'extraction des graphes d'évènements
Description: Ehab Hassan
Mardi 13 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Objets combinatoires en cryptographie et en théorie des codes
Description: Sihem Mesnager Les fonctions courbes ont été introduites par Rothaus et étudiées pourla première fois par Dillon dans sa thèse. Les fonctions courbes sontles fonctions booléennes qui sont à distance de Hamming maximale desfonctions affines. Depuis leur introduction, ellessont devenues l'un des objets les plus important en cryptographie symétrique. Unedes raisons motivant leur étude est qu'il est recommandé que lafonction booléenne utilisée pour concevoir un système de chiffrementsymétrique soit une fonction courbe pour pouvoir résister de manière optimaleaux attaques par corrélation rapides. En plus de cette importancecryptographique, les fonctions courbes ont la propriété fascinante queleurs supports sont des objets combinatoires intéressants. Leurs supportsforment des ensembles à différence, appelés ensembles àdifférence de Hadamard. Parmi les familles de fonctions courbes, il enest une qui pourrait avoir une importance grandissante dans les annéesà venir : les fonctions hyper-courbes (introduites par Youssef et Gongen 2001). Les fonctions hyper-courbes sont des fonctions courbes quiont la propriété d'être aussi à distance maximale des permutationspolynomiales. Très récemment, il a été mis en lumière que cesfonctions étaient en relation étroite avec des objets géométriquesintéressants: les hyperovales.Dans cet exposé, nous présenterons un résumé des résultats les plusimportants et de nos apports à l'étude des fonctions booléennescourbes en illustrant les liens possibles entre les fonctions courbes etdes objets combinatoires et géométriques cités précédemment. Nousprésenterons aussi le lien entre les fonctions courbes et la théoriedes codes et plus particulièrement entre certaines fonctionsvectorielles courbes et les codes minimaux (dont les propriétéscombinatoires peuvent être exploitées par les systèmes de partagede secret).
Mardi 20 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Conformal field theory approach: combinatorial aspects and applications in critical geometry
Description: Raoul Santachiara
Vendredi 23 Mai
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Opérades et Surjections
Description: Muriel Livernet Dans un premier temps j'expliquerai sur des exemples simples ce
que sont les opérades. Dans un deuxième temps j'introduirai l'opérade des
surjections et exposerai les questions combinatoires que l'on se pose afin
de résoudre des problèmes en topologie algébrique.
Samedi 24 Mai
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Polynomial-Time Search Algorithms for Combined Exponential and Classical Neighborhoods of the CARP
Description: Stefan Irnich
Mardi 27 Mai
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Statistical Data Analysis techniques for “distribution-valued data”
Description: Rosanna Verde In many real experiences, data are collected and/or represented by frequency distributions. If Y is a numerical and continuous variable, many distinct values yi  can be observed. In these cases, the values are usually grouped in a smaller number H of consecutive and disjoint bins Ih (groups, classes, intervals, etc.). The frequency distribution of the variable Y is obtained considering the number of data values nh falling in each Ih. The histogram is then the typical graphical representation for the variable Y.The interest in analyzing data expressed by frequency distributions, as well as by histograms, is evident in many fields of research. Involving the treatment of experimental data that are collected in a range of values, whereas the measurement instrument gives only approximated (or rounded) values. An example can be given by sensors for air pollution control located in different zones of an urban area. The different distributions of measured data about the different levels of air pollutants across a day, allow to compare, and then to group into homogeneous clusters, the different controlled zones.In the framework of Symbolic Data Analysis (SDA) multi-valued data, represented by an empirical distribution(like a histogram or an observed density or a quantile function) of a quantitative variable, is defined distribution-valued data, as well as, the variable which takes as values distribution-valued data, is defined as a distributional variable.Many techniques have been recently developed for this kind of data (). The comparison of empirical distribution functions is possible by using a suitable family of distances based on the Wasserstein metric that furnishes interesting interpretative results about the characteristics (or the moments) of the distributions. The Wasserstein metric is defined as the distance (in different norm) between the empirical quantile functions (the inverse of the cumulate distribution functions associated to each observed distribution).The seminar will introduce some basic statistics for distribution valued data.Novel univariate statistics emerge from the definition of a measure of variability that is related to a distance between distributions. Then, considering the ℓ2 Wasserstein distance it is possible to define a product operator between two distributions, that has allowed to propose an extension of the classical covariance and correlation measures between distributional variables.Among the techniques of Data Analysis extended to this kind of data, during the seminar, it will be presented an approach of the dynamic clustering algorithm (like Nuées Dynamiques, (Diday (1971), Diday and Simon (1976)), based on the Wasserstein distance, with the aim to discover typologies on the basis of the similarity of the observed distributions.An application of the DCA is shown in the framework of the data stream analysis in order to detect changes in the data structure.Furthermore, a simple linear regression model will be proposed as a suitable model to estimate a distributional response variable by a linear transformation of another independent distributional variable. The main idea is to use the Wasserstein metric to measure the sum of squared errors between the observed and predicted distributional data.A space dimension reduction technique (like principal component analysis) will be  also proposed to visualize the proximities between observations and relationships among quantile function on factorial plans.Some application on real and synthetic data will be shown in order to evaluate the performance of the proposed approaches.    
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: La fonction à deux points et à trois points pour les quadrangulations et cartes
Description: Eric Fusy Pour une famille F de cartes planaires on appelle "fonction à k points" la série génératrice de comptage des cartes de F avec k pointsmarqués dont les distances deux à deux sont prescrites. On sait depuis les résultats de Bouttier, Di Francesco et Guitter(s'appuyant sur une bijection de Schaeffer) que la fonction à 2 points desquadrangulations admet une expression explicite, et des réultats plusrécents de Bouttier et Guitter (s'appuyant sur une bijection de Miermont)ont établi une expression explicite pour la fonction à trois points des quadrangulations.Nous passerons en revue ces résultats et montrerons comment on peut exploiter une bijection récente due à Ambjorn et Budd pour établir desexpressions explicites pour les fonctions à deux points et à trois points des cartes générales.Travaux en commun avec Jérémie Bouttier et Emmanuel Guitter