Graph Decompositions and Length-Constrained Expanders
COM3 Level 2
MR24, COM3 02-64
Note: Bento lunch for 20 people will be served at 12pm, followed by the talk at 12:30pm.
Abstract:
Graph decompositions are ubiquitous and powerful algorithmic tools with applications in many settings of graph algorithms: sequential, parallel, distributed, dynamic, and streaming algorithms. They also give rise to simpler structures for approximating graphs such as spanners, hop-sets and shortcuts, oblivious routing, metric embeddings, vertex sparsifiers.
Length-constrained expander decomposition is an recent versatile and powerful and generalization of both
- low-diameter decomposition, which captures l_1-quantities like lengths and costs, and
- expander decomposition, which captures l_infinity-quantities like flows and congestion.
Length-constrained expander decompositions significantly extend the range of applications of graph decomposition techniques and have already led to multiple breakthrough results.
This talk will give an intuitive introduction to various aspects of length-constrained expanders and explain their applications within the broader TCS community. No prior knowledge of expander-based algorithmics is expected.
Bio:
Prof. Haeupler recently established and leads the 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 and was an Associate Professor of Computer Science at Carnegie Mellon University 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 Sproul 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.