2015


Retour à la vue des calendrier
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é l’impact 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 d’expé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