Introduction to Length-Constrained Expanders and Expander Decompositions

A Google TechTalk, presented by Bernhard Haeupler, 2023-04-12 Abstract: Expander Decompositions have become one of the most ubiquitous, elegant, and versatile tools for fast graph and network optimization algorithms. Length-Constrained Expanders are a recent powerful generalization of expanders. They capture not just (\ell^\infty-quantities like) flows, congestion, and cuts but simultaneously also control (\ell ^{1}-quantities like) lengths and costs. Length-Constrained Expanders majorly extend the problems expanders and expander decompositions can be used for. This talk gives an introduction to expanders and hop-constrained expanders, their expander decompositions, and some applications. Bio: Bernhard Haeupler is neurodiverse (ADHD & Dyslexia), a postprof at ETH Zurich, and an Adjunct Professor at Carnegie Mellon University, where they were an Assistant and Associate Professor of Computer Science from 2014 to 2022. They received their Ph.D. and M.Sc. in Computer Science from MIT, and a B.Sc., M.Sc. and Diploma in (Applied) Mathematics from the Technical University of Munich. Dr. Haeupler's research interests lie in the intersection of algorithm design, distributed and parallel computing, network optimization algorithms, and (network) coding theory. Their research, spanning over 100 articles, was recognized with several awards, including the ACM-EATCS Doctoral Dissertation Award of Distributed Computing, the George Sprowls Dissertation Award at MIT, and various best (student) paper awards. Their research has been funded by multiple prestigious grants, including a Sloan Research Fellowship, the NSF CAREER Award, and an ERC Award. A Google Talk Series on Algorithms, Theory, and Optimization