The workshop took place Friday, 25 March 2022, at the University of Liverpool, in room 6.05 (6th floor seminar room) in the EEE building.
About
In computer-science applications, the amount of memory used is often the more limiting factor compared to running time alone.
This workshop brings experts from data structures, the analysis of algorithms, and streaming algorithms together to disseminate latest developments in the field and foster new collaborations.
Program
Friday, 25 March 2022
| Schedule | (tentative) | Title |
|---|---|---|
| 09:30 - 10:15 | Sebastian Wild | Space-efficient data structures for trees and graphs |
| 10:15 - 11:00 | Rajeev Raman | Compressing Bit-Vectors |
| 11:00 - 11:30 | Coffee Break | |
| 11:30 - 12:15 | Louisa Seelbach Benkner | Empirical Entropy for Trees |
| 12:15 - 13:00 | Cécile Mailler | Voronoi cells in random trees |
| 13:00 | Reception |
Welcome & Introduction
- Sebastian Wild (University of Liverpool)
Space-efficient data structures for trees and graphs
The first part of this talk will introduce you to the fundamental ideas from succinct data structures; no prior exposure required. The second part introduces approaches and current challenges for dealing with structural data such as trees and graphs when space comes at a premium.
Invited speakers
- Rajeev Raman (University of Leicester)
Compressing Bit-Vectors - Louisa Seelbach Benkner (University of Siegen)
Empirical Entropy for Trees
Whereas for strings, there is basically one notion of empirical entropy, several different notions of empirical entropy for trees have been proposed in the past. This talk gives a survey of existing measures of empirical entropy for trees and carries out a systematic comparison of these measures. Moreover, we review a result on an entropy bound for grammar-based tree compressors from Hucke et al. (2019). - Cécile Mailler (University of Bath)
Voronoi cells in random trees
In this talk, I will introduce the problem of Voronoi cells in graphs. I will then review two results on Voronoi cells in random trees: the first one by Addario-Berry et al. (2018) on uniform plane rooted trees, and the second one by Drewitz, Heydenreich and M. (2021) on random split trees.
Support
This workshop is support by
- the London Mathematical Society through the Celebrating New Appointments Scheme,
- the Department of Computer Science of University of Liverpool, and
- the Networks Sciences & Technologies (NeST) EEECS School initiative of University of Liverpool
Contact
For questions about the organization or program, contact Sebastian Wild.