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.


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.


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.


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


For questions about the organization or program, contact Sebastian Wild.