Keynote speakers
Jessica Enright
University of Glasgow, UK
Title: Tractable problems with respect to vertex interval membership width and generalisations
Abstract
Temporal graphs are graphs whose edges are labelled with times at which they are active. Their time-sensitivity provides a useful model of real networks, but renders many problems studied on temporal graphs more computationally complex than their static counterparts. To contend with this, there has been recent work devising parameters for which temporal problems become tractable. One such parameter is vertex-interval-membership width. Broadly, this gives a bound on the number of vertices we need to keep track of at any time in order to solve any of a family of problems. We will discuss two main things: Firstly, we introduce a new parameter, tree-interval-membership-width, that generalises both vertex-interval-membership-width and several existing generalisations. Secondly, we will outline meta-algorithms for both parameters which can be used to prove fixed-parameter-tractability for large families of problems, bypassing the need to give involved dynamic programming arguments for every problem. We will give a sample application of these to a temporal graph problem.
Bernhard Haeupler
INSAIT, Sofia University "St. Kliment Ohridski", Bulgaria & ETH Zurich, Switzerland
Title: Robust Graph Decompositions and Length-Constrained Expanders
Abstract
Graph decompositions are ubiquitous and powerful algorithmic tools with applications in many settings of network algorithms: sequential, parallel, distributed, dynamic, and streaming algorithms. They also give rise to simpler structures for approximating networks such as spanners, hop-sets and shortcuts, oblivious routings, metric embeddings, and (vertex) sparsifiers.
Length-constrained expanders and length-constrained expander decompositions are a recent versatile and powerful and generalization of both
- low-diameter decomposition, which captures lā-quantities like lengths and costs, and
- expander decomposition, which captures lā-quantities like flows and congestion.
Length-constrained expander decompositions significantly broaden and extend the range of applications for network decomposition techniques ā including more robust local decompositions of particular interest in dynamic settings. This talk will give a broad introduction to graph decompositions and various aspects of length-constrained expanders and explain their applications within the broader TCS community, including recent breakthroughs in dynamic distance oracles and computing multi-commodity flows.
Bio
Bernhard Haeupler currently leads the newly established Algorithms&Theory Group at INSAIT in Sofia, Bulgaria (Institute for Computer Science, Artificial intelligence and Technology at Sofia University "St. Kliment Ohridski") and holds a post-prof / senior scientist position at ETH Zurich.
He received his PhD from MIT, was an Associate Professor of Computer Science at Carnegie Mellon University (2014-2022), and spent time at Princeton University, Microsoft Research and Google Research. Their research, spanning more than 100 papers, has been recognized with numerous awards, including the ACM-EATCS PhD Dissertation Award in Distributed Computing, the George Sprowl Dissertation Award at MIT, and best (student) paper awards at FOCS/STOC/SODA/etc. and has been funded by prestigious grants such as a Sloan Research Fellowship, an NSF Career Award, and an ERC Starting Grant.
Their research interests focus on algorithm design and analysis for problems in the intersection of (network) optimization, distributed systems and parallel computing, (de-) randomization, (network) coding theory, dynamic algorithms, and data structures.