Séminaires du LIPN
Depuis 2007, plus de 948 séminaires ont été présentés dans le laboratoire

Afficher les séminaires de

Séminaires à venir
LCR 22/11/2018 Soft modalities as prices: a game model for intuitionistic linear logic with subexponentials, par Carlos Olarte
Carlos Olarte, Universidade Federal do Rio Grande do Norte  
Salle B107, bâtiment B, Université de Villetaneuse
22/11/2018    10:30 - 12:00
Résumé :
We look at substructural calculi from a game semantic point of view, guided by certain intuitions about resource conscious and, more specifically, cost conscious reasoning. To this aim, we start with a game for aILL (affine intuitionistic linear logic), where player I defends a claim corresponding to a (single-conclusion) sequent, while player II tries to refute that claim. Branching rules for additive connectives are modeled by choices of II, while branching for multiplicative connectives leads to splitting the game into parallel subgames, all of which have to be won by player I to succeed. The game comes into full swing by using subexponentials for representing two types of options - volatile and permanent - for purchasing resources. This leads to a new type of subexponetial calculus where costs are attached to sequents. Different proofs are interpreted as more or less expensive strategies to obtain a certain resource from a bunch of resources (priced options). Finally, we generalize the concept of costs and option's prices in proofs by using a semiring structure. This general framework allows us to interpret a wider range of subexponential systems and give meaning to the use of resources in proofs in a more flexible way.
A3 22/11/2018 Apprentissage actif pour la classification des occupations du sol sur larges étendues à partir d’images multispectrales à haute résolution spatiale : Application en milieu cultivé, Lebna (Cap-Bon Tuni, par Inès Ben Slimene
Inès Ben Slimene, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
22/11/2018    12:15 - 13:30
Résumé :
Les activités anthropiques dans le bassin méditerranéen sont en forte évolution. Dans les zones agricoles, cette croissance entraîne des évolutions considérables de l'occupation du sol. Cette activité agricole exerce un impact majeur sur le fonctionnement hydrologique des paysages qui n'est identifiable qu'à une échelle bien plus large, sur plusieurs dizaines de km². Ce travail se concentre sur la classification de l'occupation du sol sur une large étendue à partir d'une image monodate à haute résolution spatiale (SPOT6/7). Dans ce contexte, les données d'apprentissage sont collectées par des enquêtes terrain, par conséquent, elles sont très limitées. Les méthodes d'apprentissage supervisées sont généralement utilisées, en supposant que la distribution des classes est stable sur toute l'image. Cependant, en pratique, on constate une distorsion des distributions des classes (apparition de nouvelles classes, disparition de classes). Ce problème, intitulé "datashift", se produit souvent sur des larges étendues. Ainsi le modèle construit sur les données d'apprentissage initiales s'avère sous optimal pour la classification de l'image entière. Pour atténuer ce problème, les techniques d'apprentissage actif définissent un ensemble d'apprentissage efficace, en l'adaptant itérativement par l'ajout des données non labellisées les plus informatives. Ces techniques permettent d'améliorer le modèle de classification tout en conservant un petit ensemble d'apprentissage initial. L'échantillonnage se base généralement sur deux métriques : l'incertitude et la diversité. Dans ce travail, on a mis l'apport des techniques d'apprentissage actif pour la cartographie de l'occupation du sol en milieu agricole, en proposant un échantillonnage adapté par parcelle. L'apport des méthodes d'apprentissage actif est validé par rapport à une sélection aléatoire des parcelles. Une métrique de diversité basée sur l'algorithme Meanshift a été proposée. Dans un deuxième temps, on a traité le sous-problème du "datashift" qui est l'apparition de nouvelles classes. on a proposé de nouvelles métriques de diversité basées sur l'algorithme Meanshift et les Fuzzy k-means ainsi qu'une nouvelle stratégie de sélection des données adaptées à la détection de nouvelles classes. Dans la dernière partie, on s'est intéressé aux contraintes spatiales induites par les observations sur terrain et on a proposé une stratégie de labellisation par points de vue qui permet de diminuer largement les coûts humains d'observations terrain tout en gardant de bonnes précisions de classification ainsi que la découverte des nouvelles classes. Les méthodes proposées ont été testées et validées avec une image multispectrale SPOT6 à 6m de résolution sur le bassin versant de Lebna, Cap-Bon, Tunisie.
Séminaires passés
LCR 13/11/2018 On importance splitting and the automation of rare event simulation, par Carlos E. Budde
Carlos E. Budde, University of Twente  
Salle A303, bâtiment A, Université de Villetaneuse
13/11/2018    12:30 - 13:30
Résumé :
In the analysis of formal models, simulation based approaches like statistical model checking offer a solution to the state space explosion that hinders verification, but may suffer from long execution times. This is exacerbated when the property value to approximate depends on an event seldom observed; in those cases rare event simulation (RES) techniques can speed up convergence by reducing the variance of the statistical estimator. However, RES techniques typically require non-trivial and domain-specific (or even model-specific) user input, which is a setback w.r.t. the push-button approach of standard model checking. In this talk I will briefly discuss methods to automate the implementation of a specific approach to RES called "importance splitting." I will overview some known implementations and discuss two algorithms recently developed to select "importance thresholds" and "splitting/effort factors," which are parameters with direct impact on the efficiency of importance splitting. A good performance of the outcomes of the algorithms proposed has been empirically demonstrated on several case studies.
LCR 05/11/2018 State Compression Based on One-Sided Communications for Distributed Model Checking, par Laure Petrucci
Laure Petrucci, LIPN, Équipe LoVe  
Salle A303, bâtiment A, Université de Villetaneuse
05/11/2018    15:00 - 16:00
Résumé :
We propose a distributed implementation of the collapse compression technique used by explicit state model checkers to reduce memory usage. This adapatation makes use of lock-free distributed hash tables based on one-sided communication primitives provided by libraries such as OpenSHMEM. We implemented this technique in the distributed version of the model checker Helena. We report on experiments performed on the Grid'5000 cluster with an implementation over OpenMPI. These reveal that, for some models, this distributed implementation can altogether preserve the memory reduction provided by collapse compression and reduce execution times by allowing the exchanges of compressed states between processes.
RCLN 05/11/2018 Learning to Navigate and Extract Information from Web Results, par Ivan Vladimir MEZA
Ivan Vladimir MEZA, UNAM Mexique  
Salle B107, bâtiment B, Université de Villetaneuse
05/11/2018    14:00 - 15:00
Résumé :
In this talk I present our progress into the ECOS-NORD project between LIPN-Paris 13 and IIMAS-UNAM at Mexico. The talk focus on our experimental setup that allows to learn to navigate web results and to extract information from them. In particular, at this stage we are focus on extracting biográfical information of researchers, in order to quantify the Mexican returning diaspora. Our experimental setup is based on a reinforcement learning setup, we use a labelled data to learn the main actions on the results grid. We will show preliminary results, and newlines of experimentation.
A3 25/10/2018 Apprentissage automatique et adaptatif pour le clustering de flux de données relationnelles, par Parisa Rastin
Parisa Rastin, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
25/10/2018    12:15 - 13:45
Résumé :
Les approches basées sur les prototypes sont très populaires en apprentissage non supervisé, en raison de la compacité du modèle résultant (les prototypes), de la puissance descriptive de ces prototypes et de la faible complexité de calcul du modèle (chaque objet est comparé à un petit nombre de prototypes). Nous proposons une approche de K-moyennes relationnelle utilisant un ensemble unique de points de support à travers le processus d'apprentissage, puis on introduit le formalisme des Coordonnées Barycentriques afin d'unifier la représentation des objets et des prototypes, ce qui permet un processus d'apprentissage incrémental simple pour le clustering relationnel. Notre motivation pratique est de réaliser un profilage en temps réel des utilisateurs connectés. Les tâches de profilage visent à reconnaître "l'état d'esprit" des utilisateurs à travers leur navigation sur différents sites en ligne.
MERCRED 03/10/2018 First Order Algorithms for Constrained Optimization Problems in Machine Learning, par Francesco Rinaldi
Francesco Rinaldi, Université de Padoue  
Salle B107, bâtiment B, Université de Villetaneuse
03/10/2018    14:00 - 15:00
Résumé :
Thanks to the advent of the "Big Data era", simple iterative first-order optimization approaches for constrained convex optimization have re-gained popularity in the last few years. In the talk, we first review a few classic methods (i.e., conditional and projected gradient method) in the context of Big Data applications. Then, we discuss both theoretical and computational aspects of some new active-set variants for those classic methods. Finally, we examine current challenges and future research perspectives. DISCLAIMER: This aimes to be a wide audience talk (for any LIPN member, Ph. D. students included) and you are not assume to know what is a "first-order optimization approach", a "conditional or projected gradient method" or an "active-set variant".
LCR 01/10/2018 One-Sided Communications for more Efficient Parallel State Space Exploration over RDMA Clusters , par Sami Evangelista
Sami Evangelista, LIPN, Équipe LoVe  
Salle A303, bâtiment A, Université de Villetaneuse
01/10/2018    15:00 - 16:00
Résumé :
This talk presetns the use of one-sided communications in the context of state space exploration. This operation is often the core component of model checking tools that explores a system state space to look for behaviours deviating from its specification. It basically consists in the exploration of a (usually huge) directed graph whose nodes and edges represent respectively system states and system changes. We revisit the state of the art distributed algorithm and adapt it to RDMA clusters with an implementation over the OpenSHMEM library and report on preliminary experiments conducted on the Grid'5000 cluster. This asynchronous approach thus reduces the significant communication costs induced by process synchronisation in two-sided communications.
LCR 27/09/2018 Arrows , par Exequiel Rivas
Exequiel Rivas, Irif  
Salle A303, bâtiment A, Université de Villetaneuse
27/09/2018    15:30 - 17:00
Résumé :
Using monads for structuring computational effects had a big impact in the functional programming community. Arrows (Hughes 2000) are a generalisation of monads which provides support for computational effects that may be partially static. This talk will begin with an introduction on the subject, and then continue to discuss one the possible semantics of arrows from a categorical perspective.
AOC 25/09/2018 Modèles d'optimisation pour le transport urbain "flexible", par Yasmin A. Rios-Solis
Yasmin A. Rios-Solis, Universidad Autónoma de Nuevo León  
Salle B107, bâtiment B, Université de Villetaneuse
25/09/2018    12:30 - 13:30
Résumé :
Je présenterai des problèmes de transport urbain (bus) qui se trouvent dans un contexte “flexible” ou plutôt, “désordonné”: chauffeurs absents, événements inattendus qui arrivent aux véhicules, pas de voie spéciale pour les bus, presque pas d’arrêts et compétition entre compagnies de transport. Pour ces problèmes, il faut de nouveau modèles d’optimisation, des preuves de complexité et de nouvelles méthodes de résolution. Au lieu de rentrer dans les détails mathématiques, je présenterai plutôt les thèmes de recherche qui émergent de ce contexte flexible.
LCR 25/09/2018 GADTs , par Flavien
Flavien, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
25/09/2018    12:30 - 15:30
Résumé :
Il s'agit d'une présentation général des GADTs par Flavien, avec une explication de leurs intérêts pratique. Cela sera suivit d'un cas d'étude présenté par Jean-Vincent sur lequel on pourra réfléchir tous ensemble. Le créneau est long, car on ira manger entre les deux parties.
LCR 24/09/2018 A UML-based Proposal for IoT System Requirements Specification, par Gianna Reggio
Gianna Reggio, DIBRIS – Università di Genova, Italy  
Salle B107, bâtiment B, Université de Villetaneuse
24/09/2018    15:00 - 16:00
Résumé :
The talk presents a preliminary version of IotReq, a method for the elicitation and specification of the requirements for an IoT system. The first task suggested by IotReq is the modelling of the domain, using the UML and following the service-oriente d paradigm, then the goals of the IoT system to build are elicited and specified, again using the UML and extending the domain model, producing a specification of the functional requirements. IotReq also provides preliminary indications for specifying the technological nonfunctional requirements. A case study, the specication of the requirements for a system to support the Genoa’s Science Festival is presented too.
LCR 20/09/2018 GdT : SL=L, par Paulin
Paulin, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
20/09/2018    10:15 - 11:30
Résumé :
groupe de travail sur le résultat d'égalité de classes SL=L (Annonce très tardive car oubliée, désolé...)
LCR 13/09/2018 CoGITARe, par Flavien Breuvart
Flavien Breuvart, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
13/09/2018    10:15 - 11:45
Résumé :
Mon ARNJCJC CoGITARe a été accepté cet été. Ce séminaire a pour but de présenter le projet, ses objectifs et ses différentes facettes en essayant de rester haut niveau.
RCLN 03/09/2018 Analysing large-scale Research Data with Semantic Technologies, par Francesco OSBORNE
Francesco OSBORNE, Knowledge Media Institute, Open University (UK)  
Salle B107, bâtiment B, Université de Villetaneuse
03/09/2018    16:00 - 17:30
Résumé :
Semantic Technologies provide useful solutions for the analysis of big scholarly data since they facilitate the integration of large datasets and support tasks such as Natural Language Processing and Information Retrieval. In particular, ontologies that describe research topics and their relationships proved to be effective tools for making sense of research dynamics, classifying publications, detecting research communities, and forecasting research trends. However, these knowledge bases are very expensive to craft and tend to become obsolete fairly quickly. In my talk, I will discuss the automatic approach that we designed to generate and update the Computer Science Ontology (CSO), a large-scale ontology of research topics including about 25K concepts. CSO has been used for supporting Springer Nature in classifying editorial products, informing marketing decisions, and evolving their internal taxonomy. I will present some systems adopting this knowledge base and describe their effect on the workflow of a major publishing company. I will also discuss the advantage of combining Machine Learning and Semantic Technologies for addressing complex tasks such as predicting research trends and forecasting technology migrations.
A3 05/07/2018 Towards more Autonomous Robots, par Eduardo Morales
Eduardo Morales, INAOE, Mexico  
Amphi Copernic, Institut Galilée, Université de Villetaneuse
05/07/2018    12:15 - 13:45
Résumé :
With the increasing incorporation of robots into daily life activities, autonomy and interaction with non expert users play a central role in robotics research. In this talk, I will describe two developments towards this aim. First I will describe how a robot can autonomously extract information from Internet to decide where to find an unknown object and how to learn on-line a recognition model. In the second part of the talk I will describe how a non-expert user can train a robot to perform simple tasks combining programming by demonstration, reinforcement learning and user's feedback.
MERCRED 04/07/2018 Cost Efficient Prediction of Wine Quality - A Machine Learning Approach, par Razvan Andonie
Razvan Andonie, Central Washington University  
Salle B107, bâtiment B, Université de Villetaneuse
04/07/2018    14:00 - 15:00
Résumé :
The quality of wines can be assessed both from chemical/biological tests and sensory tests (which rely mainly on human experts). Determining which is the subset of tests to be used is a difficult problem. Each test has its own contribution for predicting the quality of wines and, in addition, its own cost. We use our own database, consisting of 32 wine characteristics applied to 180 wine samples. In addition we use wine quality labels assigned by a wine expert. To the extent of our knowledge, this is the first study of this kind on wines from Washington State, and also the first wine study in general to include cost minimization of the measurements as a goal. Our approach is based on two stages. First, we identify reasonably good classifiers (from a given set of classifiers). Next, we search for the optimal subset of features to maximize the performance of the best classifier and also minimize the overall cost of the measurements. As a result, through our method we can answer queries like ``the best performing subset of tests for a given threshold cost’'.
RCLN 02/07/2018 Multi-Arabic Dialect Applications and Resources, par Nizar Habash
Nizar Habash, NYU Abu Dhabi  
Salle B107, bâtiment B, Université de Villetaneuse
02/07/2018    14:00 - 15:00
Résumé :
We present the Multi-Arabic Dialect Applications and Resources (MADAR) Project. MADAR is an effort to build parallel resources for 25 Arab city dialects including lexicons, parallel corpora, and orthographic and morphological annotation guidelines. The created resources have been used to develop dialect identification and machine translation applications. We discuss the challenges facing Arabic dialect modeling, as well as our solutions and results.
A3 28/06/2018 Hyperparameter Optimization for Neural Networks, par Razvan Andonie
Razvan Andonie, Central Washington University, USA  
Salle B107, bâtiment B, Université de Villetaneuse
28/06/2018    14:00 - 15:30
Résumé :
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.
MERCRED 27/06/2018 Research Efforts at the Computational Approaches to Modeling Language Lab., par Nizar Habash
Nizar Habash, NYU Abu Dhabi, Saadiyat Island  
Salle Darwin, institut galilée
27/06/2018    14:00 - 15:00
Résumé :
TBA
RCLN 25/06/2018 The Arabic Ontology and Modernization of Lexical Semantic Resources, par Mustafa Jarrar
Mustafa Jarrar, Computer Science Department, Birzeit University, Palestine  
Salle B107, bâtiment B, Université de Villetaneuse
25/06/2018    14:00 - 15:00
Résumé :
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.
A3 21/06/2018 Proposition et consommation de contenus sur le web : le problème de la diversité., par Lionel Tabourier
Lionel Tabourier, Complex Networks, LIP6  
Salle B107, bâtiment B, Université de Villetaneuse
21/06/2018    12:15 - 13:45
Résumé :
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.
LCR 15/06/2018 Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem, par Joanna Ochremiak
Joanna Ochremiak  
Salle B107, bâtiment B, Université de Villetaneuse
15/06/2018    10:30 - 12:30
Résumé :
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.
A3 14/06/2018 Deep Cooperative Reconstruction with Privacy Constraints, par Denis Maurel
Denis Maurel, ISEP, équipe RDI  
Salle B107, bâtiment B, Université de Villetaneuse
14/06/2018    12:15 - 13:45
Résumé :
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.
MERCRED 13/06/2018 Network Interdiction, par Joe Naoum-Sawaya
Joe Naoum-Sawaya, Ivey Business School, London, ON, Canada  
TBA (Institut Galilée)
13/06/2018    14:00 - 15:00
Résumé :
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.
LCR 07/06/2018 Coends and proof equivalence in MLL2, par Paolo Pistone
Paolo Pistone  
Salle B107, bâtiment B, Université de Villetaneuse
07/06/2018    11:30 - 13:00
Résumé :
> 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.
CALIN 05/06/2018 Théorie de la complexité et géométrie des orbites du déterminant et du permanent, par Christophe Tollu
Christophe Tollu, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
05/06/2018    10:30 - 12:15
Résumé :
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".
A3 31/05/2018 Graphes dynamiques - Modélisation et Clustering, par Tabea Rebafka
Tabea Rebafka, LIP6, UPMC  
Salle B107, bâtiment B, Université de Villetaneuse
31/05/2018    12:15 - 13:45
Résumé :
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.
CALIN 29/05/2018 Combinatorics of chemical reaction systems, par Nicolas Behr
Nicolas Behr, IRIF Paris VII, Endinburgh University  
Salle B107, bâtiment B, Université de Villetaneuse
29/05/2018    14:00 - 16:00
Résumé :
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.
CALIN 29/05/2018 (CIP) Discussion on graph rewriting systems (with examples and equations), par Nicolas Behr
Nicolas Behr, IRIF Paris VII, Endinburgh University  
Salle B107, bâtiment B, Université de Villetaneuse
29/05/2018    11:00 - 12:15
Résumé :
Séminaire annulé à cause de difficultés de transport. Le séminaire de 14h00 est maintenu.
MERCRED 23/05/2018 A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin Packing Problems, par Roberto Baldacci
Roberto Baldacci, Bologne  
Salle B107, bâtiment B, Université de Villetaneuse
23/05/2018    15:00 - 16:00
Résumé :
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.
MERCRED 23/05/2018 Facteurs premiers de nombres remarquables, par Florian Luca
Florian Luca, Johannesburg  
Salle B107, bâtiment B, Université de Villetaneuse
23/05/2018    14:00 - 15:00
Résumé :
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, ...
CALIN 15/05/2018 Hom-idempotent graphs, normal Cayley graphs and stable Kneser graphs, par Mario Valencia Pabon
Mario Valencia Pabon, LIPN, Univ. Paris 13  
Salle B107, bâtiment B, Université de Villetaneuse
15/05/2018    14:00 - 15:00
Résumé :
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.
AOC 15/05/2018 Strong and Cheap SDP and SOCP Hierarchies for Polynomi al Optimization, par Bissan Ghaddar
Bissan Ghaddar, University of Waterloo  
Salle B107, bâtiment B, Université de Villetaneuse
15/05/2018    12:30 - 13:30
Résumé :
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.
CALIN 15/05/2018 Phylogenetic trees modeled by increasing Schröder trees, par Mehdi Naima
Mehdi Naima, LIPN (Doctorant Équipe CALIN, dir : Olivier Bodini)  
Salle B107, bâtiment B, Université de Villetaneuse
15/05/2018    11:00 - 12:00
Résumé :
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.
MERCRED 02/05/2018 Discrete convexity and applications to combinatorics and optimization, par Gleb Koshevoy
Gleb Koshevoy, Central Institute of Economics & Mathematics  
Salle B107, bâtiment B, Université de Villetaneuse
02/05/2018    14:00 - 15:00
Résumé :
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.
CALIN 24/04/2018 Facteurs cyclotomiques des polynômes de Serre, par Florian Luca
Florian Luca, University of the Witwatersrand  
Salle B107, bâtiment B, Université de Villetaneuse
24/04/2018    14:00 - 15:00
Document attaché
Résumé :
https://lipn.fr/~cb/Seminaires/resume.php?L=1165
CALIN 24/04/2018 CIP : Théorie de Picard-Vessiot et équations différentielles non commutatives, par Hoang Ngoc Minh
Hoang Ngoc Minh, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
24/04/2018    11:00 - 12:30
Résumé :
Attention : Horaire décalé à 11h00 vu les difficultés de transport.
MERCRED 18/04/2018 Apprentissage et génération de représentations optimisées de données complexes, par Abdelkader Benyettou
Abdelkader Benyettou, Université d'Oran, Algérie  
Salle B107, bâtiment B, Université de Villetaneuse
18/04/2018    14:00 - 15:00
Résumé :
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.
LCR 06/04/2018 Session-based concurrency, reactively, par Mauricio Cano
Mauricio Cano  
Salle B107, bâtiment B, Université de Villetaneuse
06/04/2018    11:00 - 12:30
Résumé :
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.
A3 05/04/2018 Apports de la Programmation Linéaire en Nombres Entiers pour la modélisation et l'extraction d'ensembles de motifs, par Abdelkader Ouali
Abdelkader Ouali, Équipe Modèles, Agents et Décision, laboratoire GREYC, université de Caen Normandie.  
Salle B107, bâtiment B, Université de Villetaneuse
05/04/2018    12:15 - 13:45
Résumé :
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.
LCR 30/03/2018 Un calcul des séquents avec des types dépendants pour l'arithmétique classique, par Etienne MIQUEY
Etienne MIQUEY, Gallinette (Nantes)  
Salle B107, bâtiment B, Université de Villetaneuse
30/03/2018    11:00 - 13:00
Résumé :
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.
CALIN 27/03/2018 Cluster relations among Schur functions and a positivity conjecture, par Gleb Koshevoy
Gleb Koshevoy, Moscou (Poncelet Center CNRS UMI 2615)  
Salle B107, bâtiment B, Université de Villetaneuse
27/03/2018    14:00 - 15:30
Résumé :
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.
AOC 27/03/2018 Complexity of the cluster deletion problem on cographs and subclasses of chordal graphs , par Mario Valencia Pabon
Mario Valencia Pabon, Paris 13  
Salle B107, bâtiment B, Université de Villetaneuse
27/03/2018    12:30 - 13:30
Résumé :
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).
CALIN 27/03/2018 Combinatorial bases of KZn, par Gleb Koshevoy
Gleb Koshevoy, Moscou (Poncelet Center CNRS UMI 2615)  
Salle B107, bâtiment B, Université de Villetaneuse
27/03/2018    11:00 - 12:00
Résumé :
TBA (discussion)
LCR 23/03/2018 Gdt Complexité suite, par Paulin de Naurois
Paulin de Naurois, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
23/03/2018    11:00 - 12:30
Résumé :
Suite du premier gdt
CALIN 20/03/2018 On lattice polytopes, convex matroid optimization, and degree sequences of hypergraphs, par Antoine Deza
Antoine Deza  
Salle B107, bâtiment B, Université de Villetaneuse
20/03/2018    14:00 -
Résumé :
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 matroid optimization. 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 computationally prohibitive. Based on joint works with Asaf Levin (Technion), George Manoussakis (Paris Sud), Shmuel Onn (Technion).
AOC 20/03/2018 On the Interplay between Simple Mixed Integer Programs and Lot-Sizing, par Laurence A. Wolsey
Laurence A. Wolsey, CORE, Universit\'e catholique de Louvain  
Salle B107, bâtiment B, Université de Villetaneuse
20/03/2018    12:30 - 13:30
Document attaché
Résumé :
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.
CALIN 06/03/2018 Two fast parallel GCD algorithms of many integers, par Sidi Mohamed Sedjelmaci
Sidi Mohamed Sedjelmaci  
Salle B107, bâtiment B, Université de Villetaneuse
06/03/2018    14:00 -
Résumé :
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.
CALIN 20/02/2018 Disques browniens, par Jérémie Bettinelli
Jérémie Bettinelli  
Salle B107, bâtiment B, Université de Villetaneuse
20/02/2018    14:00 -
Résumé :
À 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.
LCR 16/02/2018 Des Preuves Syntactiques aux Preuves Combinatoires, par Matteo Acclavio
Matteo Acclavio, LIX  
Salle B107, bâtiment B, Université de Villetaneuse
16/02/2018    11:00 - 12:30
Résumé :
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)
LCR 02/02/2018 Probabilistic Rewriting, par Claudia Faggian
Claudia Faggian, IRIF  
Salle B107, bâtiment B, Université de Villetaneuse
02/02/2018    11:00 - 12:30
Résumé :
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.
LCR 30/01/2018 A unified framework for notions of algebraic theory, par Soichiro Fujii
Soichiro Fujii, NII Tokyo  
Salle B107, bâtiment B, Université de Villetaneuse
30/01/2018    16:30 - 18:30
Résumé :
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.
CALIN 30/01/2018 Aspects énumératifs et bijectifs des cartes combinatoires, par Wenjie Fang
Wenjie Fang  
Salle B107, bâtiment B, Université de Villetaneuse
30/01/2018    15:00 -
Résumé :
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 aspects diffé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 de Tamari, à travers de l'aspect bijectif des cartes.
AOC 30/01/2018 Decomposition methods for quadratic programming, par Emiliano Traversi
Emiliano Traversi, AOC -LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
30/01/2018    12:30 - 13:30
Résumé :
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.
RCLN 29/01/2018 Approches non supervisées pour l'extraction de relations sémantiques, par Kata Gabor
Kata Gabor, RCLN, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
29/01/2018    14:00 - 15:00
Résumé :
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.
CALIN 16/01/2018 Chute de dimension pour les marches aléatoires sur les arbres aléatoires, par Pierre Rousselin
Pierre Rousselin  
Salle B107, bâtiment B, Université de Villetaneuse
16/01/2018    14:00 -
Résumé :
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é.
CALIN 19/12/2017 Phase transition for the hard-core model in the 2-dimensional lattice, par Juan Vera Lizcano
Juan Vera Lizcano  
Salle B107, bâtiment B, Université de Villetaneuse
19/12/2017    14:00 -
Résumé :
The hard-core gas model is a natural combinatorial problem that has played an important role in the design of new approximate counting algorithms and for understanding computational connections to statistical physics phase transitions. For a graph G = (V, E) and a fugacity t > 0, the hard-core model is defined on the set of independent sets of G where each independent set I has weight w(I) = |I|^t . The equilibrium state of the system is described by the Gibbs distribution in which each independent set I has probability ~ w(I). A long-standing open problem to establish the critical fugacity t* for the hard-core gas model on the 2-dimensional integer lattice Z^2. In particular, t* is the conjectured critical point for the phase transition between uniqueness of infinite-volume Gibbs measures on Z^2 when t < t* and non-uniqueness when t > t*. Empirical results identified the critical point t* ~ 3.79. The best known bounds show 2.538 < t* < 5.3646. In this talk the techniques to obtain these bounds will be discussed. Special emphasis will be given to the lower bound, which is based on connections between the decay of correlations on the lattice and on its self-avoiding walk tree.
AOC 19/12/2017 Characterization of the Flexibility of an Energy Consumer and Optimization of its Energy Usage, par Claude Le Pape
Claude Le Pape, Schneider Electric  
Salle B107, bâtiment B, Université de Villetaneuse
19/12/2017    12:30 - 13:30
Résumé :
The exploitation of flexibility in energy production and consumption is essential to avoid costly reinforcements of the power system and maintain security of supply while increasing the penetration of renewable (and intermittent) sources of energy. Let us focus on the "demand" side, i.e., on actors which are mostly consumers of energy: manufacturing plants, water networks, commercial buildings (or even elements in a building such as an HVAC (Heating, Ventilation and Air Conditioning) system, an elevator or a pool of elevators), and aggregations of those, such as a district. These actors use energy for their own needs, i.e., manufacture and deliver products to their own customers, deliver drinkable water to their customers, provide a comfortable work place to the employees and visitors of the building, etc. They may also produce energy, either as part of the process they manage (e.g., cogeneration in an industrial plant, elevator braking energy recovery) or with energy product ion resources installed for cost reduction and security reasons. Finally, they may also have energy storage resources, which could have been installed to build flexibility or for any other reason. Part or all of the stored energy capacity can then be used to reduce operational costs. Incentives to reduce or shift energy consumption in time must be considered with respect to the main objectives (and other cost factors) of the consuming organization. The very first thing to do is to characterize the available or potential sources of flexibility and how they could be used to make gains in terms of energy, revenues and cost savings, or environmental impact. • First, there may exist options for definitive savings of energy with no significant impact on the process for which the energy is used. In general, such savings will be doable provided they have an "acceptable" impact on the process or on its outcome. For example, the capacity to slightly dim lights in an elevator enables direct and definitive energy savings. Such dimming is acceptable if it does not occur too often. • Delays in consumption are possible when a given activity can be delayed (or performed in advance) or, more generally, when savings are possible at a given time but at the expense of further consumption before or after this time. For example, if enough water is available in a water tower, one can delay for a while the pumping of water into the water tower. At some point, however, pumping will be needed to ensure the water tower gets enough water to serve the local customers. Similarly, highly consuming activities in a manufacturing plant might be avoided during a given interval of time, provided these activities are not time-critical and the corresponding products are available in stock. At some point, however, it will become necessary to perform these activities, and consume the corresponding amount of energy to replenish the stock. • If energy storage (e.g., in batteries, in the form of hot water, etc.) is possible, then the stored energy can be used to provide an apparent consumption flexibility. For example, part of the energy stored in the battery of an elevator can be used to temporarily operate the elevator with no other impact on the elevator’s process. Considered separately, such sources of flexibility induce very different optimization models: multi-criteria regulation; scheduling with energy resource constraints and costs; energy flow optimization. Things get more complex when these sources of flexibility coexist and when multiple actors, each with its own constraints and objectives, share the same energy network. Practical optimization problems will be presented, using examples from two European projects (Arrowhead and Ambassador) and from the two PhD theses of Chloé Desdouits "Reduction of electricity consumption peaks and optimization problems induced on the demand side" and Peter Pflaum "Energy management strategies for smart grids".
RCLN 18/12/2017 Semantic similarity on transcriptional regulation literature, par Oscar Lithgow
Oscar Lithgow  
Salle B107, bâtiment B, Université de Villetaneuse
18/12/2017    12:30 - 14:00
Résumé :
Experimentally generated biological information needs to be organized and structured in order to become meaningful knowledge. However, the rate at which new information is being published makes manual curation increasingly unable to cope. Therefore, new curation strategies based on natural language processing are promising alternatives. Particularly, nowadays is improbable to consider all related research and reference every single piece of knowledge contained in the publication. Here is where we believe that computers and specifically, automatic natural language processing can help to inter-connect similar conveyed ideas among a collection of articles through discover ing semantically related sentences within a set of scientific articles and delivering those meaningful relations to the end user. Given our interest in applying such approaches to the benefit of curation of the biomedical literature, specifically about gene regulation in microbial organisms, we decided to also build a corpus with graded textual similarity evaluated by curators, and designed specifically oriented to our purposes.
A3 14/12/2017 Flots de liens pour la modélisation des interactions temporelles, par Matthieu Latapy
Matthieu Latapy, Lip6, Université Pierre et Marie Curie  
Salle B107, bâtiment B, Université de Villetaneuse
14/12/2017    12:15 - 13:30
Résumé :
Etudier la structure et la dynamique des interactions revêt un caractère crucial pour la compréhension de nombreux phénomènes et pour de nombreuses applications (détection d'événements dans du trafic, détection de fraudes, recommandation de produits, optimisation de réseaux, etc). La structure de telles interactions est étudiée en utilisant des graphes ou des réseaux (ensembles de noeuds et de liens) ; leur dynamique est étudiée en utilisant des signaux ou des séries temporelles (variations d'une propriété au cours du temps) ; pour étudier la dynamique de leur structure, on utilise des séquences de graphes. Toutefois, ces approches ne capturent que de façon très limitée la nature à la fois structurelle et temporelle des interactions, qui nécessite un cadre spécifique. Nous présentons ici une généralisation des graphes, que nous appelons des flots de liens, permettant un traitement cohérent des deux aspects. Nous obtenons un langage pour l'étude directe des séquences d'interactions, similaire à celui des graphes pour l'étude des relations.
CALIN 12/12/2017 A graph-based method to randomly generate subgroups of free groups, par Pascal Weil
Pascal Weil  
Salle B107, bâtiment B, Université de Villetaneuse
12/12/2017    15:00 -
Résumé :
The study of random algebraic objects sheds a different light on these objects, which complements the algebraic and the algorithmic points of view. When it comes to finitely generated subgroups of free groups, we have a remarkable graphical representation called the Stallings graph: the Stallings graph of a subgroup H is a finite labeled graph uniquely associated with H, efficiently computed from a set of generators of H (say, given as reduced words), and from which one can efficiently compute many invariants of H. I will discuss enumerating and randomly generating finitely generated subgroups of free groups, for the distribution given by Stallings graphs: for each positive integer n, one considers the finite number of subgroups whose Stallings graph has n vertices, and one considers the uniform distribution on that set. This requires understanding the combinatorial structure of Stallings graphs, which are interesting objects per se. I will also exhibit natural properties of subgroups which are `generic' for this distribution. This is joint work with F. Bassino (LIPN) and C. Nicaud (LIGM)
LCR 08/12/2017 Réduction et Approximations Linéaires , par Luc Pellissier
Luc Pellissier, LIPN  
TBA
08/12/2017    14:00 - 17:00
Résumé :
TBA
LCR 04/12/2017 Séminaire SV : Hiba Ouni, par Hiba Ouni
Hiba Ouni  
Salle A303, bâtiment A, campus de Villetaneuse
04/12/2017    15:00 - 16:00
Résumé :
Titre : Parallel Symbolic Observation Graph Abstract: Model checking is a powerful technique for verifying and analyzing complex systems in many application fields. The analysis process of complex and concurrent systems often requires large computation resources which represents a real challenge. Even with simple configurations, the well-known state explosion problem is faced as the generated state space of such systems grows exponentially with the number of the system components. Numerous methods and techniques have been developed to overcome this problem including parallel and distributed-memory processing. In this work, we aim at improving the performances of the so called Symbolic Observation Graph (SOG) construction by using parallelization techniques. A SOG is a hybrid structure where the transitions of a system are divided into observed and unobserved ones. The nodes of this graph are then defined as sets of states linked with unobserved transitions (and encoded symbolically with a BDD) and edges are labeled with observed transitions only (and are explicitly represented). We propose two parallel algorithms to build the SOG. The first algorithm is dedicated for shared memory architectures, and is based on the distribution of the SOG construction on several threads using a dynamic load balancing scheme. The second algorithm is proposed for distributed memory architectures, and distributes the SOG construction on processes using a static load balancing scheme. These two algorithms are implemented and their performances are studied and compared to each other and to the sequential construction of the SOG.
LCR 01/12/2017 [soutenance] , par Thomas Rubiano
Thomas Rubiano, LIPN  
TBA
01/12/2017    10:00 - 13:00
Résumé :
LCR 24/11/2017 A discussion on the conjectures NP vs PSPACE and NP vs coNP, par Hermann Hauesler
Hermann Hauesler , PUC-Rio  
Salle B107, bâtiment B, Université de Villetaneuse
24/11/2017    11:00 - 12:30
Résumé :
The aim of this talk is to open a discussion on the justification of the conjectures NP = coNP and NP = PSPACE by means of purely proof-theoretical arguments.
CALIN 21/11/2017 On the polynomial part of a restricted partition function, par Karl Dilcher
Karl Dilcher  
Salle B107, bâtiment B, Université de Villetaneuse
21/11/2017    11:00 -
Résumé :
We prove an explicit formula for the polynomial part of a restricted partition function, also known as the first Sylvester wave. This is achieved by way of some identities for higher-order Bernoulli polynomials, one of which is analogous to Raabe's well-known multiplication formula for the ordinary Bernoulli polynomials. As a consequence of our main result we obtain an asymptotic expression of the first Sylvester wave as the coefficients of the restricted partition grow arbitrarily large. (Joint work with Christophe Vignat).
LCR 20/11/2017 Séminaire SV : Fadwa Rekik, par Fadwa Rekik
Fadwa Rekik, ATER à Galilée  
Salle A303, bâtiment A, campus de Villetaneuse
20/11/2017    15:00 - 16:00
Résumé :
L’architecture orientée service (SOA) est un paradigme qui offre des mécanismes permettant une grande flexibilité des architectures des systèmes logiciels tout en réduisant leurs coûts de développement puisqu’elle se base sur des entités modulaires et réutilisables appelées services. Ces services peuvent être réutilisés dans le cadre d’une composition ou d’une chorégraphie de services pour la construction de nouveaux processus métiers transverses. De son côté, le paradigme de l’Ingénierie Dirigé par les Modèles (IDM) offre au travers de ses deux principes fondateurs, l’abstraction et l’automatisation, deux moyens puissants de gestion de la complexité sans cesse croissante des systèmes. Combiner les deux paradigmes et concevoir ainsi une approche de type SOA dirigée par les modèles semble une piste prometteuse. Cependant, malgré les progrès de l’application des principes de l’IDM la spécification et le développement des applications SOA, plusieurs problèmes restent à résoudre. Un de ces problèmes est d’effectuer une vérification rigoureuse des modèles de spécification des applications orientées services. Ces modèles sont généralement composés de plusieurs vues sémantiquement liées les unes aux autres. Un deuxième problème est la transformation de ces modèles de spécification en code exécutable. En particulier, les chorégraphies de service doivent être transformées en orchestrations exécutables tout en préservant la sémantique des scénarios de haut niveau décrits par ces chorégraphies et en tenant compte des aspects critiques inhérents aux systèmes distribués tels que l’asynchronisme. La vérification de l'exécution est aussi nécessaire afin de détecter les comportements erronés lors de l’exécution. Pour relever ces défis, nous proposons une approche SOA dirigée par les modèles qui repose sur le standard OMG SoaML. Lors de la spécification, la cohérence des modèles SoaML est vérifiée en utilisant la validation statique des modèles moyennant des règles OCL que nous avons définies. Nous avons spécifié également des règles de transformation pour permettre la génération automatique d'artefacts exécutables. Enfin, nous avons défini un cadre de test à base de modèles pour vérifier la conformité de l’exécution des chorégraphies de services, incluant les orchestrateurs générés, aux modèles de spécification. L'ensemble de notre méthode a été outillé en extension de l’outil de modélisation UML, Papyrus, et de l’outil d’analyse formelle, Diversity.
LCR 16/11/2017 Réseaux de preuve pour MLL+Mix et algorithmes sur les graphes arêtes-coloriés, par Nguy?n Lê Thành D?ng
Nguy?n Lê Thành D?ng, Education national (future LIPN ?)  
Salle B107, bâtiment B, Université de Villetaneuse
16/11/2017    11:00 - 12:30
Résumé :
Le critère de correction de Danos-Regnier mène à poser le problème d'algorithmique des graphes suivant : étant donné un graphe apparié, trouver un cycle (ou un chemin) passant au plus une fois par chaque paire. Ce problème a été traité en théorie des graphes sous la forme plus générale de graphes munis d'une coloration sur leurs arêtes ("edge-colored graphs") ; la solution fait intervenir une réduction aux couplages parfaits et rejoint donc le travail de C. Retoré sur les "handsome proof-nets". Partant de cela, on obtient facilement d'une part un critère de correction pour MLL+Mix en temps linéaire, et d'autre part que le problème de correction des réseaux MLL+Mix est probablement plus difficile que celui pour MLL sans la règle Mix (qui est NL-complet). Ce dernier résultat explique que la littérature sur les critères de correction pour MLL+Mix soit plus maigre que celle pour MLL. Nous verrons également d'autres conséquences de ces liens entre logique linéaire et théorie des graphes, notamment en lien avec le graphe de dépendances d'un réseau introduit par Bagnol, Doumane et Saurin.
LCR 08/11/2017 Formal language theory beyond trees and forests , par Tobias Heindel
Tobias Heindel, University of Copenhagen  
Salle B107, bâtiment B, Université de Villetaneuse
08/11/2017    15:00 - 16:30
Résumé :
The talk presents the theorems of Myhill-Nerode and Chomsky-Schützenberger, replacing trees and words by rewriting diagrams of semi-Thue systems, which are the paradigm example of planar acyclic circuit diagrams (PLACIDs)---the “graphical syntax” of monoidal categories. The talk will focus on the proposal of a definition of recognizable language in monoidal categories, namely sets of arrows that coincide with the inverse image of their direct image under a monoidal functor to a finite monoidal category. For the case of PLACIDs, this class of languages is shown to coincide with the languages of automata in the sense of Bossut, under modest assumptions on gates of circuit diagrams; moreover, the usual notion of recognizable tree language is recovered. The talk presents the Myhill-Nerode theorem as a tool for solving Bossut's open problem of automata complementation. The remainder of the talk describes work in progress and future work, in particular the Chomsky-Schützenberger theorem for PLACIDs.
LCR 20/10/2017 Inlining après l'élimination de fermeture pour OCaml, par Pierre Chambart
Pierre Chambart, OCamlPro  
Salle B107, bâtiment B, Université de Villetaneuse
20/10/2017    11:00 - 12:30
Résumé :
Usuellement, dans les langages de haut niveau, l'inlining est fait sur un langage intermédiaire proche d'un lambda calcul, où celà revient pour les cas simple à de la beta-réduction. Pour diverses raisons, dans OCaml, nous avons décidé d'introduire un autre langage intermédiaire où les fermetures sont explicite (flambda) sur lequel les optimisations haut niveau sont effectuées. Nous discuterons des avantages et complexités qui viennent avec ce choix.
LCR 13/10/2017 Smooth models of Differential Linear Logic, par Marie Kerjean
Marie Kerjean, IRIF  
Salle B107, bâtiment B, Université de Villetaneuse
13/10/2017    11:00 - 12:30
Résumé :
Differential Linear Logic was constructed following a study of discrete vectorial models of Linear Logic. We want to extend the semantics of Linear Logic in the natural domain of continuous objects and analysis. From the basic fact that Seely's formulas is the direct interpretation of the Kernel Theorem for distributions, we explain two developments : On one hand we axiomatize a Smooth Differential Linear Logic with a graded syntax where to each solvable Linear partial differential equation one associate an exponential. We construct a model of nuclear Fréchet/ Df spaces for this syntax. On the other hand, we argue that the interpretation of the $\parr$ as Schwartz's epsilon product should be the cornestone of the construction of a smooth classical model of DiLL. From a first-model of $k$-reflexive spaces, and based on pioneering works by Kriegl, Michor and Meise, we construct a variety of (at least two) new models of DiLL. This part is joint work with Y. Dabrowski.
LCR 22/09/2017 Circular Proofs for Subtyping and Termination, par Rodolphe Lepigre
Rodolphe Lepigre, Université de Savoie  
Salle B107, bâtiment B, Université de Villetaneuse
22/09/2017    11:00 - 12:30
Résumé :
In a recent (submitted) work with Christophe Raffalli, we designed a rich type system for an extension of System F with subtyping. It includes primitive sums and products, existential types, and (co-)inductive types. Using a combination of (pointed) subtyping and circular proofs, we were able to express the system with typing and subtyping rules that are syntax-directed (up to circularity). During my talk, I will try to give you a flavour of the techniques we used. In particular, I will show how choice operators can be used to get rid of typing contexts, and to allow the commutation of quantifiers with other connectives. I will then introduce the circular proof framework that is used for handling inductive and co-inductive types in subtyping rules, and general recursion in typing rules.
LCR 30/08/2017 Coherence for skew near-semiring categories, par Tarmo Uustalu
Tarmo Uustalu, Tallinn University of Technology  
Salle B107, bâtiment B, Université de Villetaneuse
30/08/2017    11:00 - 12:30
Résumé :
We consider skew near-semiring categories, a relaxation of near-semiring categories where the unitors, associators, annihilator and distributor are not required to be natural isomorphisms, they are just natural transformations in a particular direction. We prove a coherence theorem for such categories. The theorem states that, in a free skew near-semiring category over a set of objects, any two maps between an object and an object in normal form are equal. Our main motivating examples for skew near-semiring categories are from programming with effects. While (relative) monads and lax monoidal functors are the same as skew monoids in particular skew monoidal categories, (relative) MonadPlus and Alternative instances are skew near-semiring objects. This is joint work with Mauro Jaskelioff, Exequiel Rivas and Niccolò Veltri.
LCR 07/07/2017 Partiality and container monads, par Niccolò Veltri
Niccolò Veltri, TTÜ Küberneetika Instituut  
Salle B107, bâtiment B, Université de Villetaneuse
07/07/2017    11:00 - 12:30
Résumé :
We investigate monads of partiality in Martin-Löf type theory, following Moggi’s general monad-based method for modelling effectful computations. These monads are often called lifting monads and appear in category theory with different but related definitions. In this talk, we unveil the relation between containers and lifting monads. We show that the lifting monads usually employed in type theory can be specified in terms of containers. Moreover, we give a precise characterization of containers whose interpretations carry a lifting monad structure. We show that these conditions are tightly connected with Rosolini’s notion of dominance. We provide several examples, putting particular emphasis on Capretta’s delay monad and its quotiented variant, the non-termination monad.
LCR 30/06/2017 Inductive and Functional Types in Ludics, par Alice Pavaux
Alice Pavaux, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
30/06/2017    11:00 - 12:30
Résumé :
Ludics is a logical framework in which types/formulas are modelled by sets of terms with the same computational behaviour. We investigate the representation of inductive data types and functional types in ludics. We study their structure following a game semantics approach. Inductive types are interpreted as least fixed points, and we prove an internal completeness result giving an explicit construction for such fixed points. The interactive properties of the ludics interpretation of inductive and functional types are then studied. In particular, we identify which higher-order functions types fail to satisfy type safety, and we give a computational explanation.
LCR 23/06/2017 Petite introduction à la logique catégorique, par Damiano Mazza
Damiano Mazza, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
23/06/2017    11:00 - 12:30
Résumé :
On entend dire parfois que le lambda-calcul est "le langage interne des catégories cartesiennes fermées". Le "langage interne" d'une catégorie est une notion très générale (mais, à vrai dire, pas tout à fait formelle) de logique catégorique. Dans cet exposé, j'introduirai les concepts de base pour comprendre cette notion et expliquer comment elle est reliée à la sémantique dénotationnelle.
LCR 16/06/2017 Bar-récursion, analyse et réalisabilité classique, par Hadrien Batmalle
Hadrien Batmalle, IRIF  
Salle B107, bâtiment B, Université de Villetaneuse
16/06/2017    11:00 - 12:30
Résumé :
La réalisabilité classique est une théorie née des travaux de Jean-Louis Krivine dans les années 1990, à la frontière entre la logique et l'informatique théorique. Côté informatique, elle offre un cadre adapté à l'interprétation calculatoire de preuves classiques. Côté logique, elle apparaît comme une généralisation prometteuse du forcing de Cohen. À un modèle du lambda-calcul, on peut ainsi associer un modèle de la théorie des ensembles ZF. On s'intéresse ici à des modèles de programmation vérifiant une propriété de continuité: il peut s'agir de modèles basés sur les domaines de la sémantique dénotationnelle, ou bien de modèles de termes d'une version infinitaire du lambda-calcul. Dans ces modèles, l'instruction 'quote' (qu'on utilise usuellement en réalisabilité classique pour interpréter l'axiome du choix dépendant) n'est pas disponible. On utilise donc la technique de la bar-récursion pour interpréter l'axiome du choix dépendant. Or (en considérant la réalisabilité classique comme une généralisation du forcing), il apparaît que la bar-récursion est de plus l'analogue de la condition de chaîne descendante dans les algèbres de forcing (qui correspond à une propriété de préservation des réels). On obtient alors que toute formule de l'analyse vraie dans le modèle ambiant est réalisée dans ces nouveaux modèles, ce qui nous amène à la question suivante: quel est le comportement des programmes réalisant des formules de l'analyse?
CALIN 13/06/2017 Opérades des cliques décorées, par Samuele Giraudo
Samuele Giraudo  
Salle B107, bâtiment B, Université de Villetaneuse
13/06/2017    10:30 -
Résumé :
Nous proposons une construction fonctorielle de la catégorie des magmas unitaires vers celle des opérades non symétriques. Cette construction munit l'espace des configurations de diagonales décorées dans les polygones d'une structure d'opérade. On obtient ainsi diverses nouvelles opérades sur des sous-familles particulières de tels polygones : configurations sans croisement, configurations non imbriquées, configurations de Motzkin, etc. Nous montrons aussi comment cette construction permet de donner des définitions alternatives d'opérades déjà connues comme l'opérade des simples et doubles multi-tiles (provenant de la théorie des langages) et l'opérade de gravité.
LCR 09/06/2017 An interpretation of system F through bar recursion, par Valentin Blot
Valentin Blot, Queen Mary University of London  
Salle B107, bâtiment B, Université de Villetaneuse
09/06/2017    11:00 - 12:30
Résumé :
There are two possible computational interpretations of second-order arithmetic: Girard's system F or Spector's bar recursion and its variants. While the logic is the same, the programs obtained from these two interpretations have a fundamentally different computational behavior and their relationship is not well understood. We make a step towards a comparison by defining the first translation of system F into a simply-typed total language with a variant of bar recursion. This translation relies on a realizability interpretation of second-order arithmetic. Due to Gödel's incompleteness theorem there is no proof of termination of system F within second-order arithmetic. However, for each individual term of system F there is a proof in second-order arithmetic that it terminates, with its realizability interpretation providing a bound on the number of reduction steps to reach a normal form. Using this bound, we compute the normal form through primitive recursion. Moreover, since the normalization proof of system F proceeds by induction on typing derivations, the translation is compositional. The flexibility of our method opens the possibility of getting a more direct translation that will provide an alternative approach to the study of polymorphism, namely through bar recursion.
AOC 30/05/2017 Combinatorial optimization problems in networks, par Nelson Maculan
Nelson Maculan, Federal University of Rio de Janeiro  
Salle B107, bâtiment B, Université de Villetaneuse
30/05/2017    12:30 - 13:30
Résumé :
We present optimization models with a polynomial number of variables and constraints for combinatorial optimization problems in networks: optimum elementary cycles (whose traveling salesman problem), optimum elementary paths even in a graph with negative cycles, and optimum trees (whose Steiner tree problem) problems. Computational results for the Steiner tree problem are also presented.
CALIN 23/05/2017 Magouilles diverses pour les machines à signaux, par Thierry Monteil
Thierry Monteil  
Salle B107, bâtiment B, Université de Villetaneuse
23/05/2017    14:00 -
Résumé :
Les machines à signaux sont un modèle de calcul déterministe dont espace et temps sont continus.

Si les accumulations d'événements sont interdites, ce modèle est connu pour être équivalent au modèle de BlumShubSmale linéaire. Nous construirons dans ce cadre un oracle universel optimal (en nombre de vitesses et de paramètres irrationnels). Nous verrons comment jouer au billard permet semi-décider l'algébricité d'un nombre réel alors que c'est impossible dans le modèle BSS-linéaire. Nous verrons comment modifier légèrement le modèle pour obtenir un modèle équivalent au modèle BSS standard.

Lorsque l'on permet aux accumulations d'événements de produire un signal, nous verrons, en jouant sur l'alternance discret/continu, comment construire des machines dont le pouvoir dépasse largement les modèles de calcul usuels, en particulier, nous construirons

  • une "courbe de Peano" c'est a dire une surjection de [0,1] dans [0,1]^2.
  • un "oracle universel continu", c'est à dire un machine à un paramètre M(p) telle que toute suite N->[0,1] est generèe un certain M(p).
  • une "fonction analytique universelle", c'est à dire une machine avec 2 parametres t,x telle que pour toute fonction analytique f de rayon de convergence >1, il existe t tel que f(x)=M(t,x) pour tout x dans [-1,1], en particulier, on peut calculer les fonctions exp(x), sin(), en déplaçant un curseur.
  • aussi, on peut prendre en compte la géométrie du modèle dans la formulation même de ce que peut "calculer" (ou "dessiner") une machine, pas seulement un booléen, un entier ou un réel comme dans le cas discret. Étant donnée une machine M, si certains types de collisions sont coloriés en rouge, l'ensemble de leurs accumulations au temps 1 est un compact. Il se trouve que cette restriction est la seule : il existe une machine à un parametre M(p) telle que pour tout compact K inclus dans [0,1], il existe p dans [0,1] tel que l'ensemble des accumulations rouges de M(p) au temps 1 est K.

L'exposé sera informel et sa compréhension ne nécessitera pas de prérequis.

LCR 15/05/2017 Directed homology theories for geometric models of true concurrency, par Jérémy Dubut
Jérémy Dubut, ENS Cachan  
Salle B107, bâtiment B, Université de Villetaneuse
15/05/2017    11:00 - 12:30
Résumé :
Studying a system through its geometry is the main purpose of directed algebraic topology. This topic emerged in computer science, more particularly in true concurrency, where Pratt introduced his higher dimensional automata (HDA) in 1991 (actually, the idea of geometry of concurrency can be tracked down Dijkstra in 1965). Those automata are geometric by nature: every set of n processes executing independent actions can be modeled by a n-cube, and such an automata then gives rise to a topological space, obtained by glueing such cubes together, with a specific direction of time coming from the execution flow. It then seems natural to use tools from algebraic topology to study those spaces: paths model executions, homotopies of paths, that is continuous deformations of paths, model equivalence of executions modulo scheduling of independent actions, and so on, but all those notions must preserve the direction somehow. This brings many complications and the theory must be done again, essentially from scratch. In this talk, after developing this idea of geometry of true concurrency, I will focus on homology. Homology is a nice computable tool from algebraic topology and it is a challenge in directed algebraic topology to find a satisfactory analogue that behaves well with direction. I will present our candidate of `directed homology’, called natural (or bimodule) homology. This object consists in a functor with values in modules, which looks at the classical homology of trace spaces (a nice abstraction of what we may call `space of executions’) and how those homologies evolve with time. This evolution can be studied through an abstract notion of bisimulation of functors with values in modules, that has many equivalent characterizations (using relations, using lifting properties, using Grothendieck construction, …) and whose existence is decidable in simple cases. Finally, among nice properties of our directed homology, I will show you that it is computable on simple spaces, which are already enough to model simple truly concurrent systems. Joint work with Eric Goubault and Jean Goubault-Larrecq.
LCR 12/05/2017 Monades et comonades (suite), par Flavien Breuvart
Flavien Breuvart, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
12/05/2017    11:00 - 12:30
Résumé :
Dans cette deuxième séance du GdT modades et comonades, je présenterais les monades et comonades gradées. J'insisterais, en particulier, sur ma vision de ces objets comme potentielle piste pour faire interagir interprétation abstraite et typage dans les langages fonctionnels.
A3 11/05/2017 Accountable classification without frontiers, par Khaled Belahcen
Khaled Belahcen, LGI, CentraleSupelec  
Salle B107, bâtiment B, Université de Villetaneuse
11/05/2017    12:15 - 13:30
Résumé :
We address the problem of multicriteria ordinal sorting through the lens of accountability, i.e. the ability of a human decision-maker to own a recommendation made by the system. We put forward a number of model features that would favor the capability to support the recommendation with a convincing explanation. To account for that, we design a recommender system implementing and formalizing such features. This system outputs explanations defined under the form of specific argument schemes tailored to represent the specific rules of the model. At the end, we discuss possible and promising argumentative perspectives.
AOC 09/05/2017 Derivative-Free Line search Methods for Solving Integer Programming Problems, par Francesco Rinaldi
Francesco Rinaldi  
Salle B107, bâtiment B, Université de Villetaneuse
09/05/2017    12:30 - 13:30
Résumé :
In this talk, we describe some derivative-free methods for integer programming problems with both bound constraints on the variables and general nonlinear c onstraints. The approaches combine linesearches with a specific penalty approach for handling the nonlinear constraints. The use of both suitable generated search directions and specific stepsizes in the linesearch guarantee that all the points are generated in the integer lattice. We analyze the theoretical properties of the methods and show extensive numerical experiments on both bound constrained and nonlinearly constrained problems.
LCR 05/05/2017 Why complexity theorists should care about philosophy, par Thomas Seiller
Thomas Seiller, University of Copenhagen (DIKU)  
Salle B107, bâtiment B, Université de Villetaneuse
05/05/2017    11:00 - 12:30
Résumé :
Theoretical computer science was somehow born almost a hundred years ago when logicians asked themselves the question: "What is a computable function?". This question, purely theoretical, was answered before the first computer was designed, in the form of the Church-Turing thesis: a computable function is one that can be defined in one of the following equivalent models: recursive functions, Turing machines, or lambda-calculus. The apparition of actual computing devices however made it clear from the start that another question made more sense for practical purposes, namely: "What is an *efficiently* computable function?". This question was tackled by three different work in the span of a single year, marking the birth of computational complexity. Nowadays, computational complexity is an established field: many methods and results have been obtained, and the number of complexity classes grows every year. However, a number of basic open problems remain unanswered, in particular concerning classification of complexity classes. Even worse than that, a number of results – called barriers – show that no known method will succeed in producing a new separation result, i.e. show that two classes (e.g. P and NP, or L and P) are disjoint. From a purely theoretical point of view, this lack of methods might be explained by a historic tradition of viewing programs as functions. Once this misconception identified, it points to a lack of adequate foundations for the theory of computation. Fortunately, some recent technical developments may provide a solution to this problem.
A3 27/04/2017 RoSTBiDFramework: Optimised Framework based on Rough Set Theory for Big Data Pre- processing in Certain and Imprecise Contextsble, par Zeineb Chelly
Zeineb Chelly , Aberystwyth University, Wales, UK  
Salle B107, bâtiment B, Université de Villetaneuse
27/04/2017    12:30 - 13:45
Résumé :
Over the last decades, the amount of data has increased in an unprecedented rate, leading to a new terminology: "Big Data". Big data are specified by their Volume, Variety, Velocity and by their Veracity/Imprecision. Based on these 4V specificities, it has become difficult to quickly acquire the most useful information from the huge amount of data at hand. Thus, it is necessary to perform data (pre-)processing as a first step. In spite of the existence of many techniques for this task, most of the state-of-the-art methods require additional information for thresholding and are neither able to deal with the big data veracity aspect nor with their computational requirements. This project's overarching aim is to fill these major research gaps with an optimised framework for big data pre-processing in certain and imprecise contexts. Our approach is based on Rough Set Theory (RST) for data pre-processing and Randomised Search Heuristics for optimisation and will be implemented under the Spark MapReduce model. The project combines the expertise of the experienced researcher Dr Zaineb Chelly Dagdia in machine learning, rough set theory and information extraction with the knowledge in optimisation and randomised search heuristics of the supervisor Dr Christine Zarges at Aberystwyth University. Further expertise is provided by internal and external collaborators from academic and non-academic institutions, namely Lebbah and Azzag (University of Paris 13), Shen (University of Aberystwyth), Tino (University of Birmingham), Merelo (University of Granada) and an industrial partner from France.
A3 21/04/2017 Complex network analysis in ubiquitous and social environments, par Martin Atzmueller
Martin Atzmueller, University of Kassel, Faculty of Electrical Engineering/Computer Science  
Salle B107, bâtiment B, Université de Villetaneuse
21/04/2017    15:00 - 16:30
Résumé :
In the world of today, a variety of interaction data of humans, services and systems is generated, e.g. , by sensors and social media. This enables the observation and capture of physical and social activities, and subsequent extended analysis of interactions, structures and patterns covering both online and offline contexts. This talk focuses on behavioral analytics in social media and the physical world, and presents exemplary methods and results in the context of real-world systems. Specifically, we focus on the grounding and analysis of behavior, interactions and complex structures emerging from heterogeneous data, and according modeling approaches using complex network analysis.
AOC 18/04/2017 Deriving differential approximation results for k-CSPs from combinatorial designs, par Sophie Toulouse
Sophie Toulouse, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
18/04/2017    12:30 - 13:30
Résumé :
Given two integers q, k ? 2, k-CSP?q is the unconstrained optimization problem in which variables have domain Z_q and the goal is to optimize a weighted sum of constraints, each acting on at most k of the variables. Standard inapproximability results for Max-k-CSP?q often involve balanced k-wise independent distributions over Z_q or rather equivalently, orthogonal arrays of strength k over Z_q. We here illustrate how combinatorial designs are a relevant tool in order to establish approximation results for k-CSP?q with respect to the differential approximation measure, which compares the distance between the approximate value and the worst solution value to the instance diameter. First, connecting the average differential ratio to orthogonal arrays, we deduce that this ratio is ?(1/n^(k/2)) when q = 2, ?(1/n^(k-1)) when q is a prime power and 1/q^k on (k+1)-partite instances. We also consider pairs of arrays that can be viewed as some constrained decomposition of balanced k-wise independent functions. We exhibit such pairs that allow when q > k to reduce k-CSP?q to k-CSP?k with an expansion 1/(q?k/2)^k on the approximation guarantee. This implies together with the result of [Yuri Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, 9 (1998), pp. 141–160] a lower approximability bound of 0.429/(q ? 1)^2 for 2-CSP?q. Similar designs also allow to establish that every Hamming ball with radius k provides a ?(1/n^k)-approximation of the instance diameter.
CALIN 11/04/2017 Utilisation avancée de Maple : calcul parallèle et interfaçage avec des bibliothèques externes, par Nicolas Gachadoit et Nicolas Cottereau
Nicolas Gachadoit et Nicolas Cottereau  
Salle B107, bâtiment B, Université de Villetaneuse
11/04/2017    14:00 -
Résumé :
Maple possède plusieurs milliers de fonctions, mais certains calculs spécifiques peuvent nécessiter l'utilisation de bibliothèques externes. Par ailleurs, les ordinateurs n'évoluent plus tellement dans le sens d'une augmentation de la fréquence des processeurs mais dans le sens d'une augmentation du nombre de c?urs de calcul. Cette présentation (par Nicolas Gachadoit) détaillera les fonctionnalités de Maple permettant de réaliser des calculs parallèles et de s'interfacer avec du code écrit dans d'autres langages. Il y aura également une présentation rapide (par Nicolas Cottereau) de quelques fonctionnalités de la plateforme Maple dédiée pour l?enseignement.
LCR 31/03/2017 Équivalences entre programmes, par Jean-Yves Moyen
Jean-Yves Moyen, LIPN - University of Copenhagen  
Salle B107, bâtiment B, Université de Villetaneuse
31/03/2017    11:00 - 12:30
Résumé :
Partant du théorème de Rice, on définit l'équivalence extensionelle comme "deux programmes sont équivalents si ils calculent la même fonction." Le théorème de Rice stipule alors une indécidabilité forte de cette équivalence (aucune union de classes n'est décidable). Qu'en est-il des autres équivalences entre programmes ? Certaines sont décidables (eg, avoir le même nombre de lignes de codes), d'autres non. L'ensemble des équivalences possède une structure de treillis complet et le théorème de Rice parle de l'indécidabilité d'un filtre principal de ce treillis. À partir de ces constatations, j'explore deux pistes parallèles. D'une part, quelle est l'importance de l'équivalence extensionelle dans ces résultats ? Est-ce qu'on peut obtenir d'autres résultats similaires à partir d'une autre équivalence ? D'autre part, comment étudier l'ensemble du treillis des équivalences ? Est-ce qu'on peut trouver des sous-ensembles qui conservent la structure lié à l'ordre tout en étant plus facilement manipulables (notamment, dénombrables) ?
CALIN 28/03/2017 Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints, par Sergey Dovgal
Sergey Dovgal  
Salle B107, bâtiment B, Université de Villetaneuse
28/03/2017    14:00 -
Résumé :
We show that by restricting the degrees of the vertices of a graph to an arbitrary set ?, the threshold ?(?) of the phase transition for a random graph with n vertices and m = ?(?).n edges can be either accelerated (e.g., ?(?) approx 0.38 for ? = {0,1,4,5}) or postponed (e.g., ?(?) approx 0.95 for ?={1,2,50}) compared to a classical Erd?s?Rényi random graph where ?(N)=1/2. We investigate different graph statistics inside the critical window of transition (planarity, diameter, longest path...). We apply our results to a 2-SAT model with restricted literal degrees: the number of clauses that each literal is incident to belongs to the set ?. We prove a lower bound for the probability that a formula with n variables and m=2.?(?) n clauses is satisfiable. This probability is close to 1 for the subcritical regime m=2.?.n.(1-μ.n-1/3), μ to ∞ and improves/generalizes the lower bound of Bollobás, Borgs, Chayes, Kim, and Wilson. This shows how the phase transition threshold for 2-SAT moves if we change the degrees of the literals. Joint work with Vlady Ravelomanana.
LCR 24/03/2017 Syntaxe transcendentale: seconde lecture., par Christophe Fouqueré
Christophe Fouqueré, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
24/03/2017    11:00 - 12:30
Résumé :
Suite de la première lecture: JY Girard, avec ses 3 articles sur la "syntaxe transcendentale", aborde la logique sous un angle à la fois philosophico-logique et sous un angle technique, pour aller au-delà de ce qui est fait jusqu'à présent: non seulement la logique linéaire propositionnelle mais encore le traitement de l'égalité donc du premier ordre. Modestement, je commencerai par présenter la partie technique, qui reprend et étend le modèle des réseaux de preuves, en présentant la représentation de MALL et des exponentielles.
LCR 23/03/2017 CARET Model Checking For Pushdown Systems, par Huu-Vu Nguyen
Huu-Vu Nguyen, LCR, LIPN, Paris 13  
Salle B107, bâtiment B, Université de Villetaneuse
23/03/2017    14:00 - 15:00
Résumé :
CARET (A temporal logic of calls and returns) was introduced by Alur et al. This logic allows to write linear temporal logic formulas while taking into account matching of calls and returns. However, CARET model checking for Pushdown Systems (PDSs) was never considered in the literature. Previous works only dealt with the model checking problem for Recursive State Machine (RSMs). While RSMs are a good formalism to model sequential programs written in structured programming languages like C or Java, they become non suitable for modeling binary or assembly programs, since, in these programs, explicit push and pop of the stack can occur. Thus, it is very important to have a CARET model checking algorithm for PDSs. We tackle this problem in this paper. We also consider CARET model checking with regular valuations, where the set of configurations in which an atomic proposition holds is a regular language. We reduce these problems to the emptiness problem of Büchi Pushdown Systems. We implemented our technique in a tool, and we applied it to different case studies. Our results are encouraging. In particular, we were able to apply our tool to detect several malwares. This is a joint work with Tayssir Touili.
LCR 17/03/2017 Des preuves, oui, mais formelles !, par Micaela MAYERO
Micaela MAYERO, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
17/03/2017    11:00 - 12:30
Résumé :
Dans cet exposé, très informel, lui, je parlerai de l'évolution des outils de preuves formelles ces 20, voire ces 30, dernières années. Nous nous appuierons sur quelques exemples afin de montrer comment les formalisations contribuent à la fois au développement de ces outils via des avancés théoriques majeurs ainsi qu'aux domaines qui s'engagent peu à peu dans leur utilisation. Suite à une première partie accessible à tout public, nous parlerons de la logique sous-jacente à l'un des système connaissant le plus d'avancées et de changements: Coq. Nous aborderons les évolutions de la théorie des types avec (im)prédicativité, la logique classique avec le choix de la totalité et d'autres avancées, pour finir, si nous avons le temps, par quelques mots sur CoqHoTT et l'axiome d'univalence.
LCR 16/03/2017 Preserving Partial Order Runs in Parametric Time Petri Nets, par Cesar Rodriguez
Cesar Rodriguez, LCR, LIPN, Paris 13  
Salle B107, bâtiment B, Université de Villetaneuse
16/03/2017    15:30 - 16:30
Résumé :
Parameter synthesis for timed systems aims at deriving parameter valuations satisfying a given property. In this paper we target concurrent systems; it is well known that concurrency is a source of state-space explosion, and partial order techniques were defined to cope with this problem. Here we use partial order semantics for parametric time Petri nets as a way to significantly enhance the result of an existing synthesis algorithm. Given a reference parameter valuation, our approach synthesizes other valuations preserving, up to interleaving, the behavior of the reference parameter valuation. We show the applicability of our approach using acyclic asynchronous circuits. Join work with Thomas Chatain and Étienne André.
CALIN 14/03/2017 Géométrie combinatoire : densité d'hypergraphes et méthode probabiliste, par Xavier Goaoc
Xavier Goaoc  
Salle B107, bâtiment B, Université de Villetaneuse
14/03/2017    14:00 -
Document attaché
Résumé :
Un hypergraphe à n sommets dont aucune projection sur k sommet n'est complète a au plus O(n^{k-1}) arêtes. Ce résultat, découvert simultanément par Sauer, Vapnick-Chervonenkis et Perles-Shelah au début des années 1970, est fondamental en apprentissage. En géométrie combinatoire et algorithmique, il permet souvent de contrôler la complexité (globale) d'une structure par sa "densité" locale. J'introduirai à ce mécanisme avant de présenter quelques extensions récentes, obtenues conjointement avec Boris Bukh (https://arxiv.org/abs/1701.06632), qui permettent un controle plus fin de la complexité. L'exposé ne supposera aucune connaissance préalable et un des ingrédients sera une construction probabiliste.
LCR 10/03/2017 Retrofitting linear types, par Arnaud Spiwack
Arnaud Spiwack, Tweag I/O  
Salle B107, bâtiment B, Université de Villetaneuse
10/03/2017    11:00 - 12:30
Résumé :
Type systems based on linear logic and their friends have proved that they are both capable of expressing a wealth of interesting abstractions. Among these the ability to mix garbage-collected and explicitly managed data in the same language. This is of prime interest for distributed computations that need to reduce latency induced by GC pauses: a smaller GC heap is a happier GC heap. I had always had the belief that to add linear types to a language was a rather intrusive procedure and that a language with linear types would basically be an entirely new language. The Rust language is a case in point: it has a linear-like type system, but it's a very different language from your run-of-the-mill functional language. This turns out not to be the case: this talk presents a way to extend a functional programming language. We are targeting Haskell but there is little specific to Haskell in this presentation. I will focus mostly on the type system and how it can be generalised: among other things the type system extends to dependent types.
LCR 09/03/2017 Hybride Modelling, Analysis and Quantitative Verification of Large Biological Regulatory Networks, par Louis Fippo Fitime
Louis Fippo Fitime, LCR, LIPN, Paris 13  
Salle B107, bâtiment B, Université de Villetaneuse
09/03/2017    10:30 - 11:30
Résumé :
Biological Regulatory Networks (BRNs) are usually used in systems biology for modelling, understanding and controlling the dynamics of different biological functions (differentiation, proliferation, proteins synthesis, apoptose) inside cells. Those networks are enhanced with experimental data that are nowadays more available which give an idea on the dynamics of BRNs components. Formal analysis of such models fails in front of the combinatorial explosion of generated behaviours despite the fact that BRNs provide abstract representation of biological systems. This thesis handles hybrid modelling, the simulation, the formal verification and control of Large Biological Regulatory Networks. This modelling is done thanks to stochastic automata networks, thereafter to Process Hitting by integrating time-series data. Firstly, this thesis proposes a refining of the dynamics by estimation of stochastic and temporal (delay) parameters from time-series data and integration of those parameters in automata networks models. This integration allows the parametrisation of the transitions between the states of the system. Then, a statistical analysis of the traces of the stochastic simulation is proposed to compare the dynamics of simulations with the experimental data. Secondly, this thesis develops static analysis by abstract interpretation in the automata networks allowing efficient under- and over-approximation of quantitative (probability and delay) reachability properties. This analysis enables to highlight the critical components to satisfy these properties. Finally, taking advantage from the previous developed static analyses for the reachability properties in the qualitative point of view, and from the power of logic programming (Answer Set Programming), this thesis addresses the domain of control of system by proposing the identification of bifurcation transitions. Bifurcations are transitions after which the system can no longer reach a state that was previously reachable.
AOC 07/03/2017 Valid quadratic inequalities for convex and some non-convex quadratic sets, par Julio César Góez
Julio César Góez  
Salle B107, bâtiment B, Université de Villetaneuse
07/03/2017    11:30 - 12:30
Résumé :
In recent years, the generalization of Balas disjunctive cuts for mixed integer linear optimization problems to mixed integer non-linear optimization problems has received significant attention. Among these studies, mixed integer second order cone optimization (MISOCO) is a special case. For MISOCO one has the disjuncti ve conic cuts approach. That generalization introduced the concept of disjunctive conic cuts (DCCs) and disjunctive cylindrical cuts (DCyCs). Specifically, it showed that under some mild assumptions the intersection of those DCCs and DCyCs with a closed convex set, given as the intersection of a second order cone and an affine set, is the convex hull of the intersection of the same set with a linear disjunction. The key element in that analysis is the use of pencils of quadrics to find close forms for deriving the DCCs and DCyCs. In this talk we present an overview of the DCCs main results and we use the same approach to show the existence of valid conic inequalities for hyperboloids and non-convex quadratic cones when the disjunction is defined by parallel hyperplanes. Joint work with Miguel F. Anjos.
RCLN 06/03/2017 Automatic Deception Detection in Text Applying Topic Modeling Algorithms, par Hiram Calvo
Hiram Calvo, Centro de Investigación en Computación, IPN  
Salle B107, bâtiment B, Université de Villetaneuse
06/03/2017    14:00 - 15:00
Résumé :
We deal with deceptive text identification by using different kinds of features: a continuous semantic space model based on latent Dirichlet allocation topics (LDA), one-hot representation (OHR), syntactic information from syntactic n-grams (SN), and lexicon-based features using the linguistic inquiry and word count dictionary (LIWC). We will present experiments with several combinations of these features were tested to assess the best source(s) for deceptive text identification aiming to present a state of the art performance. We conducted our tests on three different available corpora: a corpus consisting of 800 reviews about hotels, a corpus consisting of 600 reviews about controversial topics, and a corpus consisting of 236 book reviews. Additionally, we present an analysis on which features lead to either deceptive or truthful texts, finding that certain words can play different roles (sometimes even opposing ones) depending on the task being evaluated. We will present results of experiments in one-domain setting by training and testing our models separately on each dataset (with fivefold cross-validation); in a mixed-domain setting by merging all datasets into one large corpus (again, with fivefold cross-validation), and finally, with cross-domain setting: using one dataset for testing and a concatenation of all other datasets for training.
LCR 03/03/2017 Introduction à la théorie de la complexité géométrique, d'après K. Mulmuley, par Luc Pellissier
Luc Pellissier, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
03/03/2017    11:00 - 12:30
Résumé :
La théorie de la complexité géométrique est un programme de recherche porté par Ketan Mulmuley, qui vise à résoudre des questions de complexité après les avoir traduites comme des inclusions de surfaces algébriques représentant des groupes de symétries. Après avoir présenté la théorie avec beaucoup de recul, on présentera un résultat de séparation obtenu ainsi (entre P et une classe ad hoc).
LCR 02/03/2017 Reachability Analysis of Pushdown Systems with an Upper Stack, par Adrien Pommellet
Adrien Pommellet, LCR, LIPN, Paris 13  
Salle B107, bâtiment B, Université de Villetaneuse
02/03/2017    14:00 - 15:00
Résumé :
Pushdown systems (PDSs) are a natural model for sequential programs, but they can fail to accurately represent the way an assembly stack actually operates. Indeed, one may want to access the part of the memory that is below the current stack or base pointer, hence the need for a model that keeps track of this part of the memory. To this end, we introduce pushdown systems with an upper stack (UPDSs), an extension of PDSs where symbols popped from the stack are not destroyed but instead remain just above its top, and may be overwritten by later push rules. We prove that the sets of successors post* and predecessors pre* of a regular set of configurations of such a system are not always regular, but that post* is context-sensitive, so that we can decide whether a single configuration is forward reachable or not. In order to underapproximate pre* in a regular fashion, we consider a bounded-phase analysis of UPDSs, where a phase is a part of a run during which either push or pop rules are forbidden. We then present a method to overapproximate post* that relies on regular abstractions of runs of UPDSs. Finally, we show how these approximations can be used to detect stack overflows and stack pointer manipulations with malicious intent.
AOC 02/03/2017 On big data, optimization and learning, par Prof. Andrea Lodi
Prof. Andrea Lodi, Department of Mathematics and Industrial Engineering - École Polytechnique de Montréal  
Salle B107, bâtiment B, Université de Villetaneuse
02/03/2017    12:30 - 13:30
Résumé :
In this talk I review a couple of applications on Big Data that I personally like and I try to explain my point of view as a Mathematical Optimizer -- especially concerned with discrete (integer) decisions -- on the subject. I advocate a tight integration of Machine Learning and Mathematical Optimization (among others) to deal with the challenges of decision-making in Data Science. For such an integration I try to answer three questions: 1) what can optimization do for machine learning? 2) what can machine learning do for optimization? 3) which new applications can be solved by the combination of machine learning and optimization?
LCR 24/02/2017 Expérimenter un modèle de programmation fonctionnel, réactif et concurrent (à environnement global) compositionnel en OCaml., par Jean-Vincent Loddo
Jean-Vincent Loddo, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
24/02/2017    11:00 - 12:30
Résumé :
Note: Il s'agit d'un groupe de travail informel et non d'une présentation. Abstract: OCaml est un langage nativement multi-paradigme, permettant un style de programmation fonctionnel, impératif et objet. Une librairie de processus légers (threads), fournie avec le langage et s'appuyant sur le système d'exploitation sous-jacent, permet d'ajouter à la liste précédente le style de programmation concurrent à mémoire partagée (ou environnement "global"). Or, cette variante du style concurrent paraît tellement difficile et source d'erreurs ("race conditions", "deadlocks", "resource starvation") qu'elle est souvent réputée impraticable. Ce constat a probablement influencé la recherche sur les paradigmes concurrents, qui s'est orientée, depuis la fin des années '70 et début '80, sur le modèle opposé des algèbres de processus, c'est-à-dire à environnement "local" ou échange de messages (CSP de Hoare 1985, CCS de Milner 1989, LOTOS ISO 1985). L'intérêt soulevé par les mémoires transactionnelles à partir des années 2000, témoigne toutefois d'un retour à la mode de l'environnement global dans un cadre de programmation multi-thread. Entre-temps, un autre style de programmation, très adapté aux programmes interactifs et typiquement avec interface graphique, le style "réactif" (ou programmation événementielle) a fait brèche dans la culture des programmeurs et le support de ce style est offert dans un nombre grandissant de langages "mainstream", impératifs ou fonctionnels. Tout cela peut s'ajouter et se combiner à l'ancienne notion de "promesse" ("future") proposée comme mécanisme de synchronisation de programmes hybrides fonctionnels-concurrents (Friedman & Wise 1976, Baker & Hewitt 1977). Dans cet exposé nous présenterons une tentative de synthèse des styles fonctionnel, réactif et concurrent à environnement global, qui soit compositionnelle, c'est-à-dire permettant de composer des éléments modulaires. Cette solution, qui prend la forme contingente d'une librairie OCaml, a été inspirée par l'implémentation courante du logiciel Marionnet (simulateur de réseaux TCP/IP) et devrait, à terme, permettre la ré-implantation d'une partie critique du code.
RCLN 20/02/2017 L’évolution des bases de connaissances RDF, par Fatma Chamekh
Fatma Chamekh  
Salle B107, bâtiment B, Université de Villetaneuse
20/02/2017    14:00 - 15:00
Résumé :
En 2006, Tim Berners-Lee a présenté le web de données ou données liées (Linked data web of data) comme une nouvelle perspective du web sémantique. L'idée est de privilégier la publication des données structurées sur le web, sous forme d'un réseau global d'informations, en les reliant les unes aux autres. Cependant, des nouveaux jeux de données sont créés ou d’autres sont mises à jour. D’où, les bases de connaissances RDF ont besoin d’évoluer. Dans ce séminaire, je présenterai mes travaux de recherche qui porte sur l’évolution des bases de connaissances RDF en se focalisant sur la qualité des données et la gestion des versions. Dans un premier temps, j’exposerai mon travail de thèse. Il s’agit d’une approche pluridisciplinaire qui allie le paradigme agent aux technologies du web sémantique. Cette approche emploie les capacités cognitives et réactives des agents pour gérer la qualité des données et la gestion des versions. Dans un deuxième temps, je présenterai un bref aperçu sur mes travaux de recherche actuels.
LCR 10/02/2017 Syntaxe transcendentale: première lecture., par Christophe Fouqueré
Christophe Fouqueré, LIPN  
Salle B107, bâtiment B, Université de Villetaneuse
10/02/2017    11:00 - 12:30
Résumé :
JY Girard, avec ses 3 articles sur la "syntaxe transcendentale", aborde la logique sous un angle à la fois philosophico-logique et sous un angle technique, pour aller au-delà de ce qui est fait jusqu'à présent: non seulement la logique linéaire propositionnelle mais encore le traitement de l'égalité donc du premier ordre. Modestement, je commencerai par présenter la partie technique, qui reprend et étend le modèle des réseaux de preuves, en présentant la représentation de MALL et des exponentielles.
LCR 09/02/2017 Malware Detection Based On Graph Classification, par Khanh Huu The Dam
Khanh Huu The Dam, LCR, LIPN, Paris 13  
Salle B107, bâtiment B, Université de Villetaneuse
09/02/2017    13:00 - 14:00
Résumé :
Malware detection is nowadays a big challenge. The existing techniques for malware detection require a huge effort of engineering to manually extract the malicious behaviors. To avoid this tedious task of manually discovering malicious behaviors, we propose in this paper to apply learning for malware detection. Given a set of malwares and a set of benign programs, we show how learning techniques can be applied in order to detect malware. For that, we use abstract API graphs to represent programs. Abstract API graphs are graphs whose nodes are API functions and whose edges represent the order of execution of the different calls to the API functions (i.e., functions supported by the operating system). To learn malware, we apply well-known learning techniques based on Random Walk Graph Kernel (combined with Support Vector Machines). We can achieve a high detection rate with only few false alarms (98.93% for detection rate with 1.24% of false alarms). Moreover, we show that our techniques are able to detect several malwares that could not be detected by well-known and widely used antiviruses such as Avira, Kaspersky, Avast, Qihoo-360, McAfee, AVG, BitDefender, ESET-NOD32, F-Secure, Symantec or Panda. This is a joint work with Tayssir Touili.
AOC 07/02/2017 Reformulations de programmes quadratiques convexes en nombres entiers, par Dominique Quadri
Dominique Quadri, Université Paris-Sud  
Salle B107, bâtiment B, Université de Villetaneuse
07/02/2017    12:30 - 13:30
Résumé :
La programmation quadratique en nombres entiers trouve de nombreuses applications dans le monde réel. Il semble important de développer des méthodes de résolution exactes permettant de résoudre en des temps CPU limités de tels problèmes. Or de nos jours les solveurs de programmation linéaire sont de plus en plus efficaces. C'est pourquoi cet exposé est axé sur des reformulations de programmes quadratiques en variables entières en programmes linéaires.
A3 02/02/2017 Complétion de valeurs manquantes à l'aide d'un surfeur aléatoire, par François Rioult
François Rioult, GREYC Université de Caen  
Salle B107, bâtiment B, Université de Villetaneuse
02/02/2017    12:15 - 13:30
Résumé :
Dans les contextes réels, des valeurs manquantes figurent dans les données et il est possible d'obtenir des informations contextuelles expliquant l'absence de valeur : y-a-t-il une valeur spécifique pour un autre attribut ? y-a-t-il une autre valeur manquante ? etc. Ces informations contextuelles peuvent être organisées sous forme de graphe, où un surfeur aléatoire fera émerger l'explication la plus probable pour cette valeur manquante. Cette explication donne des indications sur une potentielle complétion.