Graph decompositions, such as low-diameter and expander decompositions, are very powerful. They have 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 emerging powerful 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.
This significantly extends the range of applications of graph decomposition techniques.
Our workshop 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.
Bernhard Haeupler (ETH Zurich & Carnegie Mellon University)
Thatchaphol Saranurak (University of Michigan)
Bernhard Haeupler (ETH Zurich & Carnegie Mellon University)
Length-Constrained Expander: motivation and overview [pptx, pdf]
Thatchaphol Saranurak (University of Michigan)
Basics of Length-Constrained Expander and the existence of Low-Step Flow Emulators [video, pptx, pdf]
Antti Roeyskoe (ETH Zurich)
Bypassing the Flow-Decomposition Barrier: O(1)-Approximate Multicommodity Flow in (m+k)^{1+eps} Time [pdf]
Ellis Hershkowitz (Brown University)
Fast algorithms for length-constrained expander decompositions [pdf]
Thatchaphol Saranurak (University of Michigan)
Robustness of Length-Constrained Expanders: Dynamic Distance Oracles and Overview [video, pptx, pdf]
Yaowei Long (University of Michigan)
Robustness of Length-Constrained Expanders: Techniques [video, pptx, pdf]
Bernhard Haeupler (ETH Zurich & Carnegie Mellon University)
Future Promising Directions
If you have listened to the talks and would like to learn more about some keywords, below is a summary of the list of papers related to those keywords.
[Haeupler, Raecke, Ghaffari STOC'22]
The first proof of the existence/algorithms of LC-expander decomposition
Oblivious routing from LC-expander hierarchy
[Haeupler, Hershkowitz, Saranurak STOC'23]
Length-constrained flow algorithms
[Haeupler, Huebotter, Ghaffari'22]
Cut-matching game for LC-expanders with constant length slack
See also, Distance-matching game [Chuzhoy SODA'23]
[Haeupler, Hershkowitz, Tan FOCS'24]
New algorithms for LC-expander decomposition.
Union of sparse LC-cuts is a sparse LC-cut (proved via low arboricity of parallel greedy graphs from [Haeupler, Hershkowitz, Tan]): reduces expander decomposition to finding a sparse LC-cut
Finding sparse LC-cuts via cut-matching game for LC-expanders
[Haeupler, Hershkowitz, Li, Roeyskoe, Saranurak STOC'24]
Low-step flow emulators
Low-step multicommodity flow with O(1)-length-approximation and n^\eps-congestion-approximation
Final result: O(1)-approximate multicommodity flow with
[Haeupler, Long, Saranurak FOCS'24]
Dynamic LC-expander decomposition
Dynamic vertex sparsifiers
Localized version of length-contained flow algorithms in [HHS'23]
Final result: Deterministic O(1)-approximate dynamic distance oracles