Mardi 5 Mai
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Comptage et énumération de surfaces plates, formes quasimodulaires |
Description: |
Samuel Lelièvre |
Jeudi 7 Mai
Heure: |
15:00 - 18:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Présoutenance de thèse : A left/right dynamic on permutations |
Description: |
Quentin de Mourgues Soit s une permutation dans Sigma_n.Soit i(s)=s(1), j(s)=s^{-1}(1),Soit C_k le cycle 1>2>...>(k-1)>1 (k,k+1,..,n points fixes).On definit L et R comme suit:L(s) = C_{j(s)}.s etR(s) = s.C_{i(s)}^{-1}Il est facile de voir que L et R sont inversibles, la dynamique L/R partitionne donc Sigma_n en classes d'équivalence qui sont des graphes orientés uniformes (une arête entrant/sortant par "couleur" L et R) fortement connexes.Dans cet exposé, on étudiera ces classes : leur nombre, leur taille, leur structure, etc. |
Heure: |
16:00 - 19:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Présoutenance de thèse : Tilings |
Description: |
Alexandra Ugolnikova |
Lundi 11 Mai
Heure: |
14:00 - 15:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Structured Prediction, Optimization and Deep Syntax |
Description: |
Caio Filippo Corro A sequence of words is not a sufficient representation for efficient processing of natural languages. In order to extract information from sentences, we need to decode their underlying abstract structure(s). Unfortunately, grammar formalisms that are able to properly capture complicated phenomena encountered in natural languages (wh-movements, cross-serial dependencies,...) have a repelling complexity. The work in this thesis will focus on developing efficient parsing algorithms for various formalisms (TAG, LCFRS, RCG) using optimization methods (Lagrangian relaxation, dual decomposition). |
Mardi 12 Mai
Heure: |
11:00 - 14:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Various aspects of automaton synchronization |
Description: |
Mikhael Berlinkov |
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
EXACT APPROACHES TO THE NETWORK DESIGN PROBLEM WITH RELAYS |
Description: |
Ivana Ljubic This work considers the Network Design Problem with Relays (NDPR). The NDPR arises in the context of network design when given node-pairs need to communicate with each other, but, due to signal deterioration, communication paths have to respect given distance limits. To cover longer distances, equipment for signal regeneration (i.e., relays) may be required. To enable required communications, one has to upgrade the network: by installing new links, by installing relays on the existing network, or by a combination of both. Besides applications in network design, the NDPR arises in the context of e-mobility where relays model charging stations for electric cars and edge costs correspond to road tolls.
In contrast to previous work on the NDPR, which was mainly focused on heuristic approaches, we propose new exact approaches based on different mixed integer linear programming formulations for the problem. We develop Branch-and-Price and Branch-Price-and-Cut algorithms that build upon models with an exponential number of constraints and variables. In a computational study, we analyze the performance of these approaches for instances with different characteristics.
This is a joint work with M. Leitner, M. Riedler and M. Ruthmair |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Énumération d'automates minimaux et fonctions de parking |
Description: |
Jean-Baptiste Priez |
Mardi 19 Mai
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Approximating the energy storage problem and other continuous dynamic programs |
Description: |
Giacomo Nannicini We study the problem of optimally managing a source of renewable energy connected to the power grid, a battery, and potentially a household or some other form of energy sink. This problem can be naturally cast as a dynamic program. We propose a model for this problem that subsumes other models in the literature, and we analyze its complexity, showing that in the deterministic setting the problem is solvable in polynomial time, but it becomes #P-hard in the stochastic setting. A variant of the problem that is commonly encountered in practice (i.e. the one where selling energy to the power grid is not allowed) admits a Fully Polynomial Time Approximation Scheme (FPTAS) if the energy levels are discretized; but what about the more natural case where energy is considered a continuous variable? We show that in this case, the problem belongs to a class of convex continuous dynamic programs that admits neither a multiplicative nor an additive approximation. We then show that we can construct a novel type of approximation scheme, where additive and multiplicative approximation are required at the same time but both can be arbitrarily small. We discuss a preliminary computational evaluation of this new type of approximation scheme for continuous convex dynamic programs, showing its potential. |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Explicit forms and combinatorial content of Levy stable distributions |
Description: |
Katarzyna Górska |
Jeudi 21 Mai
Heure: |
14:30 - 15:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Reachability Preservation Based Parameter Synthesis for Timed Automata |
Description: |
Étienne André The synthesis of timing parameters consists in deriving conditions on the timing constants of a concurrent system such that it meets its specification. Parametric timed automata are a powerful formalism for parameter synthesis, although most problems are undecidable. We first address here the following reachability preservation problem: given a reference parameter valuation and a (bad) control state, do there exist other parameter valuations that reach this control state iff the reference parameter valuation does? We show that this problem is undecidable, and introduce a procedure that outputs a possibly underapproximated answer. We then show that our procedure can efficiently replace the behavioral cartography to partition a bounded parameter subspace into good and bad subparts; furthermore, our procedure can even outperform the classical bad-state driven parameter synthesis semi-algorithm, especially when distributed on a cluster. |
Mardi 26 Mai
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Efficient Algebraic Diagonals and Walks |
Description: |
Louis Dumont The diagonal of a multivariate power series F is the univariate power series Diag F generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. Westudy algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case Diag F is an algebraic function. We propose an algorithm that computes an annihilating polynomial forDiag F. Generically, it is its minimal polynomial and is obtained in time quasi-linear in its size. We show that this minimal polynomial has an exponential size with respect to the degree of the input rational function. Throughout the talk, we use a common problemof counting certain lattice walks to illustrate the capacities and limits of our tools. |
Mercredi 27 Mai
Heure: |
14:00 - 16:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Logics via algebras and substitutions |
Description: |
Antonino Salibra In this talk we present a translation of formulas and models of classical and non-classical logics into factor algebras. The correspondence: Propositional variables --- operator of decompositions Logical operations --- substitutions Formulas --- algebraic terms Models --- factor algebras, provides a uniform calculus of provability for all the logics which admit the translation. Many examples will be discussed: classical logic, intuitionistic logic, linear logic, many-valued logics. |
Mardi 2 Juin
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Explicit forms and combinatorial content of Levy stable distributions |
Description: |
Katarzyna Górska |
Vendredi 5 Juin
Heure: |
11:00 - 12:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Configuration Structures |
Description: |
Clément Aubert A standard contextual equivalence for process algebras is strong barbed congruence. Configuration structures are a denotational semantics for processes in which one can define equivalences that are more discriminating, i.e. that distinguish the denotation of terms equated by barbed congruence. Hereditary history preserving bisimulation (hhpb) is such a relation. We define a strong back and forth barbed congruence using a reversible process algebra and show that the relation induced by the back and forth congruence is equivalent to hhpb. Hence we give a characterization of hhpb as a contextual equivalence in a reversible process algebra.
Joint work with Ioana Cristescu. |
Mardi 9 Juin
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Calculabilité et pavages |
Description: |
Pascal Vanier |
Vendredi 12 Juin
Heure: |
11:00 - 12:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
On the dependencies of logical rules |
Description: |
Alexis Saurin Many correctness criteria have been proposed since linear logic was introduced and it is not clear how they relate to each other. We present proof-nets and their correctness criteria from the perspective of dependency, as introduced by Mogbil and Jacobé de Naurois.
More precisely, we introduce a new correctness criterion, called DepGraph, and show that together with Danos' contractibility criterion and Mogbil and Naurois criterion, they form the three faces of a notion of dependency which is crucial for correctness of proof-structures.
Finally, we extract the logical meaning of the dependency relation and show that it allows to recover and characterize some constraints on the ordering of inferences which are implicit in the proof-net.
Joint work with Marc Bagnol and Amina Doumane. |
Mardi 16 Juin
Heure: |
12:15 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Évaluation et sélection des collaborateurs en clustering collaboratif |
Description: |
Guénaël Cabanes L'objectif du clustering collaboratif est de révéler la structure commune de données qui sont réparties sur différents sites. Le concept fondamental du clustering collaboratif est d'avoir des algorithmes qui s'exécutent localement mais qui collaborent en échangeant de l'information sur les partitions locales des données obtenues par chaque algorithme. Ce type d'apprentissage collaboratif peut être appliqué à un grand nombre de tâches, y compris le clustering multi-vues, la segmentation de données distribuées, le regroupement et l'analyse multi-échelle et multi-expert, etc.... Cette étude introduit un nouveau cadre de collaboration qui permet à un large éventail d'algorithmes de collaborer ensemble. L'originalité de la méthode proposée est qu'elle rend possible la collaboration entre des algorithmes de différentes familles. Nous avons aussi analysé limpact de la diversité entre les collaborateurs et de la qualité des collaborateurs sur la qualité de la collaboration, afin de définir des pondérations à appliquer à chaque collaborateur. Nous avons testé l'efficacité de notre approche à partir dexpériences sur des jeux de données réels. |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Hopf algebras and towers of monoids |
Description: |
Aladin Virmaux |
Jeudi 18 Juin
Heure: |
14:30 - 15:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Model-checking for efficient malware detection |
Description: |
Tayssir Touili The number of malware is growing extraordinarily fast. Therefore, it is important to have efficient malware detectors. Malware writers try to obfuscate their code by different techniques. Many of these well-known obfuscation techniques rely on operations on the stack such as inserting dead code by adding useless push and pop instructions, or hiding calls to the operating system, etc. Thus, it is important for malware detectors to be able to deal with the program's stack. In this talk I will show a new model-checking approach for malware detection that takes into account the behavior of the stack. Our approach consists in : (1) Modeling the program using a Pushdown System (PDS). (2) Introducing new logics, called SCTPL and SLTPL, to represent the malicious behavior. SCTPL (resp. SLTPL) can be seen as an extension of the branching-time temporal logic CTL (resp. the linear-time temporal logic LTL) with variables, quantifiers, and predicates over the stack. (3) Reducing the malware detection problem to the model-checking problem of PDSs against SCTPL/SLTPL formulas. We show how our new logics can be used to precisely express malicious behaviors that could not be specified by existing specification formalisms. We then consider the model-checking problem of PDSs against SCTPL/SLTPL specifications. We provide efficient algorithms to solve these problems. We implemented our techniques in a tool, and we applied it to detect several viruses. Our results are encouraging. In particular, our tool was able to detect more than 800 viruses. Several of these viruses could not be detected by well-known anti-viruses such as Avira, Avast, Norton, Kaspersky and McAfee. |
Mardi 23 Juin
Heure: |
10:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Journée MathStic 'Marches dans le quart de plan' |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Uniform random generation of walks in the quarter-plane |
Description: |
Marni Mishna |
Heure: |
15:00 - 18:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Walks in the quarter plane with arbitrary big jumps |
Description: |
Kilian Raschel |
Mercredi 24 Juin
Heure: |
10:15 - 13:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Accueil de la Journée MathStic 'Combinatoire et probabilités' (! c'est un mercredi) |
Heure: |
10:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Journée MathStic 'Marches dans le quart de plan' (! c'est un mercredi) |
Heure: |
11:30 - 14:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Statistics of the real roots of real random polynomials |
Description: |
Grégory Schehr |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Uniform random generation of walks in the quarter-plane |
Description: |
Marni Mishna |
Heure: |
14:00 - 15:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Uniform random generation of walks in the quarter-plane |
Description: |
Marni Mishna |
Heure: |
15:00 - 18:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Walks in the quarter plane with arbitrary big jumps |
Description: |
Kilian Raschel |
Heure: |
17:00 - 20:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
pot de clôture |
Lundi 29 Juin
Heure: |
12:15 - 13:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
BE-PUM: A tool of Binary Emulation for Pushdown Model generation |
Description: |
Quan Thanh Tho In this talk, we present the tool BE-PUM (Binary Emulation for PUshdown Model generation) for binary analysis. As suggested by its name, BE-PUM generates pushdown model, which is considered as a control flow graph (CFG) combined with a memory execution model. BE-PUM also introduces a concolic approach in order to generate CFG in a more precise manner. As such, BE-PUM is able to handle various popular obfuscation techniques of malwares, such as indirect jump or self- modification code. In experiments, we are able to produce models for around 1700 samples of real malware. Compared to JakStab and IDA Pro, two state-of-the-art tools in this field, BE-PUM shows better tracing ability, sometimes with significant differences. |
Heure: |
14:00 - 15:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Annotation et exploration de textes de spécialité - fragments d'une expérience |
Description: |
François Lévy, Sylvie Szulman Nous avons (ré)écrit un outil de manipulation conjointe d'annotations et de textes annotés, Omtat (One More Textual Annotation Tool) qui permet de visualiser les annotations et d'en ajouter, Les annotations, inspirées de Brat (Brat rapid annotation tool) peuvent porter sur une zone discontinue et qualifier des annotations-arguments. Un moteur de requêtes permet d'extraire et d'exploiter des ensembles de documents, phrases et annotations. Les premiers tests portent sur des textes de biologies et sur des textes juridiques, pour lesquels nous avons créé quelques types d'annotations spécialisées. Nous en profiterons pour dire en quoi spécialiser les annotations en tenant compte du domaine nous parait utile et tenter de convaincre que les résultats peuvent être intéressants. |
Jeudi 2 Juillet
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Solving the quadratic shortest path problem |
Description: |
Borzou Rostami Finding the shortest path in a directed graph is one of the most important combinatorial optimization problems, having applications in a wide range of fields. In its basic version, however, the problem fails to represent situations in which the value of the objective function is determined not only by the choice of each single arc, but also by the combined presence of pairs of arcs in the solution. In this paper we model these situations as a Quadratic Shortest Path Problem, which calls for the minimization of a quadratic objective function subject to shortest-path constraints. We prove strong NP-hardness of the problem and analyze polynomially solvable special cases, obtained by restricting the distance of arc pairs in the graph that appear jointly in a quadratic monomial of the objective function. Based on this special case and problem structure, we devise fast lower bounding procedures for the general problem and show computationally that they clearly outperform other approaches proposed in the literature in terms of their strength. |
Heure: |
14:30 - 15:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Action synthesis for branching time logic: theory and applications |
Description: |
Micha? Knapik Action-Restricted Computation Tree Logic (ARCTL) is a simple extension of CTL, proposed by Pecheur and Raimondi, where the actions allowed along the considered runs can be explicitly indicated by path selectors. ARCTL allows to express properties such as "a safe state is unavoidable for every path built from Forward and Left actions", denoted by AF{Forward,Safe}safe. By replacing the concrete sets of actions with free variables we obtain a parametric version of the logic pmARCTL, where properties such as AF{X}safe are allowed, where X is a parameter. We introduce a fixed-point theory that allows for the exhaustive synthesis of all the valuations of the variables which make the pmARTCL formulae hold in a given model. The theory has been implemented in an open source stand-alone tool and evaluated on scalable examples with promising results. |
Mardi 7 Juillet
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Nonlinear dynamics and complex systems [TBC] |
Description: |
Joshua Socolar |
Vendredi 24 Juillet
Heure: |
11:00 - 12:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Monetary Economics Simulation: Stock-Flow Consistent Invariance, Monadic Style |
Description: |
Antoine Kaszczyc |
|
|