"Compressed Data Structures" & "Flow of Knowledge in Information Networks" By Dr. Baffier

Date

Tuesday, August 21, 2018 - 11:00 to 12:00

Location

Meeting Room C016 - Lab1 Bldg

Description

Neural Computation Unit (Doya Unit)  would like to invite you to the following seminars.

Speaker: Dr. Jean-François Baffier
Bio:
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 Graph 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. More recently, he focuses on transmission of knowledge in various networks.
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 Institute of Technology (Japan).

[Talk 1]
Date: Tuesday, August 21
Time: 11:00-12:00

Title: Compressed Data Structures

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(n1+1/logp 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 https://github.com/Azzaare/CompressedStacks.cpp.git.
The article presenting this work is available on arxiv: https://arxiv.org/abs/1706.04708 and was presented and published at SEA 2018 last June.

[Talk 2]
Date: Wednesday, August 22
Time: 11:00-12:00

Title: Flow of Knowledge in Information Networks

Abstract:
Not only the amount of information composing nowadays networks is voluminous, the entanglement of those information brings out new kinds of interpretations. It also requires new techniques. A first part of this entanglement is brought by networks composed by layers of different nature. For instance, an Internet provider could have an optical fiber layer and a satellite layer. Data rate, delay, robustness, coverage, and other properties of such layers are quite different and need to be handled in specific manners. However, those two layers interact at various points in the network, and, as such, cannot be considered independently.
The second kind of entanglement is related to the information itself. In a classical monoplex model, a node can send information to Alice and Bob, but it does not take into account that some information transmitted to Alice can also be (re-)transmitted to Bob - with a possible treatment of the information. Multiplex networks, by their nature, represents this kind of connections. Although our research can be applied to various type of networks and datasets, we chose to consider Citation Networks as a general multilayer/multiplex network. Citation networks cover both the multilayer part (publications, authors, institutions, fields, journals, countries, ...) and the multiplex entanglement of data. We cover comparisons of our multiplex network metrics framework with some basic metrics like the impact factor and the h-index.
This work is available as open-access journal article as: http://rdcu.be/AiWK

We hope to see many of you at the seminar.
Sincerely,
Kikuko Matsuo
Neural Computation Unit

All-OIST Category: 

Intra-Group Category


Subscribe to the OIST Calendar: Right-click to download, then open in your calendar application.