moteur de recherche

Séminaire A3SI+LRT - Jean-Francois Baffier
Séminaire A3SI+LRT - Jean-Francois Baffier
22-Jun-2018 14:30
Age: 1 year

Jean-Francois Baffier (Tokyo Institute of Technology)

Study of compressed stack algorithms in limited memory environment

Room 260 (ESIEE PARIS)

Abstract: The need to run algorithms on limited-memory devices motivated our consideration for data structure in the settings where there is only a limited amount of memory available (apart from the input representation). We proposed a practical implementation of the theoretical work of Barba et al.. In their work, they introduce a class of algorithms called stack algorithms: algorithms that scan the input in a streaming fashion and have a stack as their space bottleneck. For those algorithms, Barba et al. introduce a new data structure, called compressed stack, that gives a general time-space trade-off: they can reduce the amount of memory used by the algorithm at the cost of increasing running time. Specifically, stack algorithms can run in O(n^(1+1/log_p(n) ) ) time using O(p.log_p(n) ) space for any parameter p ∈ {2,...,n} (instead of Θ(n) time and space when a normal stack is used).

All of our algorithms are available in C ++ (and Julia) under MIT licenses at

The article presenting this work is available on arxiv:

Jean-Francois Baffier graduated Master course at University Paris XI in 2011 and got Ph.D. from the University of Tokyo in 2015. He was a member of the ERATO Kawarabayashi Large Project from May 2015 to August 2017 in Tokyo and Sendai.

His main research topic covers modeling of failures and routing in Networks. Other research topics involve Game analysis and AI for Games (in particular Starcraft), but also Local Search algorithm (HPC) and limited memory algorithms.

He is currently supported by the Japanese Society for the Promotion of Science as a JSPS-CNRS research fellow (Sept. 2017-2019) and hosted at the Tokyo Intistute of Technology (Japan).

<- Back to: Accueil