Introduction to Length-Constrained Expanders and Expander Decompositions @GoogleTechTalks
Introduction to Length-Constrained Expanders and Expander Decompositions  @GoogleTechTalks
Uploaded April 2023 | Updated November 2026, 6 days ago
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
Introduction to Length-Constrained Expanders and Expander DecompositionsOne Tree to Rule Them All: Polylogarithmic Universal Steiner TreesUnderstanding Trade-offs Between Worst-case Differential Privacy Guarantees & Real Threat ModelsGraph Attention RetrospectiveMapping from Training Data to Predictions with Datamodels2023 Blockly Developer Summit DAY 1-14: BlocksCAD - Math + Coding + DesignCharles Hoskinson | CEO of Input Output Global | web3 talks | Jan 5th 2023 | MC: Marlon RuizFixed-point Error Bounds for Mean-payoff Markov Decision ProcessesRepresentational Strengths and Limitations of TransformersLow Cost High Power Membership Inference AttacksDisparate Privacy Risks from Medical AI - An Investigation into Patient-level Privacy RiskUnderstanding LLMs Like Physicists: Observation, Hypothesis, Experimentation, and Prediction
Google TechTalks |

Introduction to Length-Constrained Expanders and Expander Decompositions

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER