Mardi 6 Septembre
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Génération des alignements d'arbres |
Description: |
Julien Courtiel L'alignement d'arbres est la généralisation naturelle de la notion classique d'alignement de séquences. Elle est utilisée dans de nombreux domaines, y compris pour la comparaison de structures secondaires d'ARN (ce qui nous intéressera aujourd'hui). Nous allons donc comprendre comment explorer l'espace des alignements d'arbres et comment déduire des algorithmes efficaces pour comparer les ARN.Cet exposé introduit ainsi les notions d'alignement de séquences et d'arbres et décrit le problème d'ambiguïté qui point quand nous voulons générer de manière correcte les alignements d'arbres. Pour résoudre ce problème d'ambiguïté dans le contexte des alignements d'arbres, nous donnons un schéma de décomposition sous la forme de grammaire sans contexte. Cela conduit à de nombreux résultats : propriétés statistiques sur les larges structures d'ARN, algorithmes efficaces d'échantillonnage...Ces travaux, en collaboration avec Cédric Chauve et Yann Ponty, illustrent le fait que la combinatoire peut être un puissant couteau suisse pour traiter des problèmes algorithmiques qui apparaissent dans de nombreux champs appliqués. |
Vendredi 9 Septembre
Heure: |
10:30 - 12:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Les algèbres implicatives, d'après A. Miquel (1ère partie) |
Description: |
Luc Pellissier Les structures implicatives sont des structures algèbriques extrèmement simples généralisant à la fois les modèles dénotationnels du ?-calcul et les algèbres de Heyting. Elles permettent donc d'interpréter à la fois les termes et les types, qui se retrouvent ainsi identifiés.
Les structures implicatives sont donc une fondation naturelle pour le forcing (où l'on interprète les formules dans des algèbres de Boole dans le cas classique ou de Heyting dans le cas intuitionniste) et la réalisabilité (où l'on interprète les formules par des ensembles de ?-termes). On verra qu'en effet, une structure implicative munie d'un quotient adéquat engendre un tripos, c'est-à-dire un modèle de la logique intitutionniste d'ordre supérieure (imprédicative). |
Mardi 20 Septembre
Heure: |
10:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Shuffle d'arbres |
Description: |
Eric Hoffbeck Les shuffles (battages) jouent un rôle important dans la compréhension du produit d'ensembles simpliciaux, qui intervient à de nombreux endroits en topologie algébrique. Récemment, une généralisation des ensembles simpliciaux a été introduite : les ensembles dendroidaux (on remplace les {0,1,...,p} (avec leur ordre total) par des arbres (avec leur ordre partiel)). La catégorie des ensembles dendroidaux est également munie d'un produit, où interviennent des shuffles d'arbres.Dans cet exposé, après une brève motivation topologique, j'introduirai cette notion de shuffles d'arbres, en donnant plusieurs définitions équivalentes et de nombreux exemples. Je présenterai ensuite quelques propriétés algébriques et combinatoires de ces shuffles.Mon exposé est basé sur un travail en commun avec Ieke Moerdijk. |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Counting observables of colored tensor models |
Description: |
Joseph Ben Geloun Colored tensor models generate Feynman graphs representing discrete geometries.They form as an interesting approach of quantum gravity where discrete geometriesrepresent quanta of spacetime. The coloring in tensor models improves a lot the topology type ofthese discrete structures and this helps a lot in their understanding. In my presentation,I will review (in a pedestrian way) their construction and then list basic properties of their observables.Recalling that an observable simply means in this context a convolution or contraction of tensors,observables of colored tensor models map to bi-partite colored graphs. A first question that one can addressis can we enumerate these observables? I will explain how such an enumeration is possible andhow it has lead us to an intriguing bijection with the counting of branched covers of the 2-sphere. |
Vendredi 23 Septembre
Heure: |
10:30 - 12:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Les algèbres implicatives, d'après A. Miquel (2ème partie) |
Description: |
Luc Pellissier Cest la suite, donc, on parlera de passoires https://www.youtube.com/watch?v=TMt6TDQe4nQ |
Mardi 27 Septembre
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
TBA |
Description: |
Quan Shi |
Mardi 4 Octobre
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Évaluation multi-précision rigoureuse de fonctions D-finies en Sage |
Description: |
Marc Mezzarobba Je présenterai une implémentation en développement d'algorithmes d'évaluation numérique de fonctions D-finies (c.-à-d. solutions d'équations différentielles linéaires à coefficients polynomiaux), pour le logiciel de calcul formel libre SageMath. Ce nouveau package a vocation à remplacer NumGfun, un package un peu similaire pour Maple que j'ai présenté au séminaire CALIN il y a quelques années. Si le temps le permet, je dirai aussi quelques mots des algorithmes originaux utilisés.La fonctionnalité centrale de ce code est le « prolongement analytique numérique » d'une fonction D-finie, qui fournit une approximation de la matrice envoyant un jeu de conditions initiales en un point donné du plan complexe sur les conditions « initiales » qui définissent la même fonction au voisinage d'un autre point. Le prolongement analytique numérique permet de calculer des valeurs ou encore des approximations polynomiales de fonctions D-finies n'importe où sur leur surface de Riemann, des matrices de monodromie d'opérateurs différentiels, etc. Le code traite complètement le cas limite important de conditions initiales généralisées données en un point singulier régulier de l'opérateur. Il peut donc être utilisé pour calculer des matrices de connexion entre singularités régulières, ce qui est utile notamment en combinatoire analytique. Par ailleurs, il s'agit d'une implémentation rigoureuse, au sens où elle renvoie des intervalles qui (sauf bug !) contiennent à coup sûr le résultat mathématique exact. |
Jeudi 6 Octobre
Heure: |
10:30 - 11:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Solving the Asymmetric Travelling Salesman Problem |
Description: |
Luis Gouveia There are many ways of modelling the Asymmetric Traveling Salesman Problem (ATSP) and the related Precedence Constrained ATSP (PCATSP). In this talk we present new formulations for the two problems that can be viewed as resulting from combining precedence variable based formulations, with network flow based formulations. As suggested in [1], the former class of formulations permits to integrate linear ordering constraints. The motivating formulation for this work is a complicated and "ugly" formulation that results from the separation of generalized subtour elimination constraints presented in [2] (see also [1]). This so called "ugly" formulation exhibits, however, one interesting feature, namely the "disjoint subpaths" property that is further explored to create more complicated formulations that combine two (or three) "disjoint path" network flow based formulations and have a stronger linear programming bound. Some of these stronger formulations are related to the ones presented for the PCATSP in [3] and can be viewed as generalizations in the space of the precedence based variables. Several sets of projected inequalities in the space of the arc and precedence variables and in the spirit of many presented in [1] are obtained by projection from these network flow based formulations. Computational results will be given for the ATSP and PCATSP to evaluate the quality of the new models and inequalities. References: [1] L. Gouveia and P. Pesneau. On extended formulations for the precedence constrainted asymmetric traveling salesman problem. Networks, 48(2):77{89, 2006. [2] L. Gouveia and J. M. Pires. The asymmetric travelling salesman problem: On generalizations of disaggregated Miller-Tucker-Zemlin constraints. Discrete Applied Mathematics, 112:129{145, 2001.
Joint work with Pierre Pesneau (University of Bordeaux), Mario Ruthmair (University of Vienna) and Daniel Santos (University of Lisbon) |
Heure: |
13:00 - 15:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Automatic Extraction of Malicious Behaviors |
Description: |
Khanh-Huu-The Dam The number of new malwares is increasing everyday. Thus 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, we propose in this paper an approach to automatically extract the malicious behaviors. We model a program using an API call graph, and we represent the malicious behaviors using a malicious API graph. We then reduce the malicious behavior extraction problem to the problem of retrieving from the benign and malicious API call graphs the set of subgraphs that are relevant for malicious behaviors. We solve this issue by applying and adapting well-known efficient Information Retrieval techniques based on the TFIDF scheme. We use our automatically extracted malicious behavior specification for malware detection using a kind of product between graphs. We obtained interesting experimental results, as we get 99.04% of detection rate. Moreover, we were able to detect several malwares that well-known and widely used antiviruses such as Panda, Avira, Kaspersky, Avast, Qihoo- 360, McAfee, AVG, BitDefender, ESET-NOD32, F-Secure, and Symantec could not detect.
This is a joint work with Tayssir Touili. |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Évaluation multi-précision rigoureuse de fonctions D-finies |
Description: |
Marc Mezzarobba |
Mardi 11 Octobre
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Non-commutative differential equations and (some) geometrical hints |
Description: |
Gérard Duchamp On prendra appui sur les intégrales itérées des systèmesfuschsiens pour proposer une théorie des équations différentiellesnon-commutatives. Plusieurs surprises et cadeaux nous attendentdans cette exploration. |
Lundi 17 Octobre
Heure: |
14:00 - 15:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Framester: A Wide Coverage Linguistic Linked Data Hub |
Description: |
Mehwish Alam Semantic web applications leveraging NLP can benefit from easy access to expressive lexical resources such as FrameNet. However, the usefulness of FrameNet is affected by its limited coverage and non-standard semantics. The access to existing linguistic resources is also limited because of poor connectivity among them. We present some strategies based on Linguistic Linked Data to broaden FrameNet coverage and formal linkage of lexical and factual resources. We created a novel resource, Framester, which acts as a hub between FrameNet, WordNet, VerbNet, BabelNet, DBpedia, Yago, DOLCE-Zero, as well as other resources. Framester is not only a strongly connected knowledge graph, but also applies a rigorous formal treatment for Fillmore's frame semantics, enabling full-fl edged OWL querying and reasoning on a large frame-based knowledge graph. We also describe Word Frame Disambiguation, an application that reuses Framester data as a base in order to perform frame detection from text, with results comparable in precision to the state of the art, but with a much higher coverage. Open issues and current research directions will be also presented. |
Mardi 18 Octobre
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Lower bounds in resource constrained shortest path algorithms |
Description: |
Axel Parmentier Resource constrained shortest path problems arise naturally as pricing sub-problems of column generation approaches to a wide range of routing and scheduling problems. The algorithms for these problems rely on dominance relations between paths to discard partial solutions in an enumeration of all the paths. It is well known that the use of bounds on paths resources in addition to dominance relations strongly accelerates these algorithms. Nonetheless, there is still no standard procedure to build such bounds in non-linear or stochastic settings. We provide such a bounding procedure and sho w its efficiency on several deterministic and stochastic path problems. Besides, enumeration algorithms exhibit poor performances when the number of constraints increases. We show that using sets of bounds instead of single bounds enable to discard more paths and thus to tackle better with these difficult instances. Finally, we prove the relevance of these procedures in the context of column generation on industrial instances of the airline crew pairing problem. |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Combinatoire des mots |
Description: |
Johan Nilsson |
Jeudi 20 Octobre
Heure: |
15:30 - 16:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Integer-Complete Synthesis for Bounded Parametric Timed Automata |
Description: |
Étienne André Ensuring the correctness of critical real-time systems, involving concurrent behaviors and timing requirements, is crucial. Parameter synthesis aims at computing dense sets of valuations for the timing requirements, guaranteeing a good behavior. However, in most cases, the emptiness problem for reachability (i.e. whether there exists at least one parameter valuation for which some state is reachable) is undecidable and, as a consequence, synthesis procedures do not terminate in general, even for bounded parameters. In this paper, we introduce a parametric extrapolation, that allows us to derive an underapproximation in the form of linear constraints containing all the integer points ensuring reachability or unavoidability, and all the (non-necessarily integer) convex combinations of these integer points, for general PTA with a bounded parameter domain. Our algorithms terminate and can output constraints arbitrarily close to the complete result. Joint work with Didier Lime and Olivier H. Roux. |
Vendredi 21 Octobre
Heure: |
11:00 - 12:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Some interplays between proof theory and computational complexity |
Description: |
Anupam Das Proof complexity is the branch of proof theory concerned with the size of proofs. Due to old and well-known results of Cook and Reckhow, many important questions about computational complexity are equivalent to natural problems in proof complexity. For instance, coNP = NP just if there is an 'efficient' proof system for classical propositional logic. I will survey a now well-developed line of work on the proof complexity of 'deep inference' systems which has culminated in several novel phenomena in proof complexity, including improved bounds for monotone proof systems. I will also discuss remaining open problems in the area and some of their consequences.
A closely related area to proof complexity is bounded arithmetic, which studies weak fragments of arithmetic whose representable functions are typically feasible complexity classes, via bounds on quantifiers. They also act as uniform versions of corresponding propositional systems, forming a three-way correspondence. I will show how this methodology can be extended to certain deep inference and monotone systems via intuitionistic versions of bounded arithmetic, making use of a novel technique that combines the usual 'witness function method' of bounded arithmetic with realisability style extraction. I will further motivate the study of such theories in 'linear logic' in order to address the remaining correspondences, and present some recent work along this line.
Finally I will present an upcoming research project that aims to unify various strands of this research in order to develop a comprehensive approach to monotone complexity classes. |
Mardi 25 Octobre
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
TBA |
Description: |
Vincent Pilaud |
|
|