Why this workshop?

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.

Organizers

Bernhard Haeupler (ETH Zurich & Carnegie Mellon University)

Thatchaphol Saranurak (University of Michigan) 

Confirmed Speakers

Bernhard Haeupler (ETH Zurich & Carnegie Mellon University)

Ellis Hershkowitz (Brown University)

Yaowei Long (University of Michigan)

Antti Ryoeskoe (ETH Zurich)

Thatchaphol Saranurak (University of Michigan)

Schedule

Day 1: Tuesday, June 25 2024, 9-11 am PT

• Overview: What is a Length-Constrained Expander?  

• Existence of Low-Step Flow Emulators

Day 2: Wednesday, June 26 2024, 9-11 am PT

• Bypassing the Flow-Cut Gap: O(1)-Approximate Multicommodity Flow in m^{1+eps} Time 

• Algorithmic Components for Length-Constrained Expanders: Fat-LDD, Cut-Matching Game, and Expander Routing

Day 3: Thursday, June 26 2024, 9-11 am PT

• Robustness of Length-Constrained Expanders: Improved Dynamic Distance Oracles

• Future Promising Directions