SEMINARS

Month Week Day
May 2018
Monday Tuesday Wednesday Thursday Friday Saturday Sunday

Category: SeminarsA data structure for analyzing spatio-temporal correlations of alarms, by Anne Bouillard (Nokia)

A data structure for analyzing spatio-temporal correlations of alarms, by Anne Bouillard (Nokia)

Category: SeminarsMinimization of Circuit Registers: Retiming Revisted, by Bruno Gaujal (Polaris).

Minimization of Circuit Registers: Retiming Revisted, by Bruno Gaujal (Polaris).

Category: SeminarsGeorge Arvanitakis (Polaris)

George Arvanitakis (Polaris)
  • April 26, 2018 @ Bâtiment IMAG (106) -- Approximate equilibria of Colonel Blotto games, by Quan Vu (Polaris and Nokia)

    Resource allocation games are commonly used to model problems in many domains ranging from security to advertising. One of the most important resource allocation games is the Colonel Blotto game: Two players distribute a fixed budget of resources over multiple battlefields to maximize the aggregate value of battlefields they win, each battlefield being won by the player who allocates more resources to it. Despite its long-standing history and importance, the continuous version of the game---where players can choose any fractional allocation---still lacks a complete Nash equilibrium solution in its general form with asymmetric players' budgets and heterogeneous battlefield values.

    In this work, we propose an approximate equilibrium for this general case. We construct a simple strategy (the independently uniform strategy) and prove that it is an epsilon-equilibrium. We give a theoretical bound on the approximation error in terms of the number of battlefields and players’ budgets which identifies precisely the parameters regime for which our strategy is a good approximation. We also investigate an extension to the discrete version (where players can only have integer allocations), for which we proposed an algorithm to compute very efficiently an approximate equilibrium. We perform numerical experiments that guarantee that we can "safely" use this strategy in practice. Our work extends the scope of application of Colonel Blotto games in several practical cases, especially with large games' parameters (e.g. in advertisements, voting, security, etc.,)

  • May 4, 2018 @ Bâtiment IMAG (206) -- A data structure for analyzing spatio-temporal correlations of alarms, by Anne Bouillard (Nokia)

    In this talk, I will present a data structure for the analysis of correlations of alarms, for root-cause analysis or prediction purposes. This is a joint work with Marc-Olivier Buob and Maxime Raynal (intern). A sequence of alarms is modeled by a directed acyclic graph. The nodes of the graph are the alarms, that are represented by a symbol and an interval of time. An arc of the graph is interpreted as a potential causality between two alarms. I will first show how to build a "compact" structure storing all the potential causal sequences of alarms and then how to weight this structure so that the actual correlations can be detected. The efficiency of the approach will be demonstrated on toy examples.

  • May 24, 2018 @ -- Minimization of Circuit Registers: Retiming Revisted, by Bruno Gaujal (Polaris).

    Given a digital circuit (made of logical gates and registers), is it possible to construct a new circuit computing the same function but using less registers?
    We show that the minimal number of registers is the size of a minimal cut in a periodic infinite graph corresponding to an unfolding of the initial circuit.
    We also show when it coincides with the retiming technique introduced by Leiserson and Saxe and when it outperforms optimal retiming.

  • May 31, 2018 @ -- George Arvanitakis (Polaris)

    TBA

  • June 7, 2018 @ -- Seminaire Yves Robert

    TBA

  • June 21, 2018 @ -- Franck Iutzeler

    TBA

Comments are closed