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. |
|
|