Joint Theory Lunch Seminar / Doctoral Speaking Skills Talk - Henry Fleischmann
— 1:00pm
Location:
In Person
-
Gates Hillman 8102
Speaker:
HENRY FLEISCHMANN
,
Ph.D. Student
Computer Science Department
Carnegie Mellon University
https://hfleischmann3.github.io/index.html
Expander decompositions are well-established as a central tool in undirected graph algorithms, facilitating an avalanche of breakthrough results over the past two decades. Recently they have also found a home in directed graph algorithms, powering recent breakthroughs in max flow and dynamic shortest path.
In this talk, I discuss recent work advancing the state of the art of directed expander decompositions. I'll describe techniques from the undirected setting and discuss how to extend them to the directed setting to achieve a faster directed algorithm. Our methods are gardening-inspired: turning a hedge into a neat and tidy row of bushes turns out to be just like finding an expander decomposition!
Based on arXiv:2507.09729. Joint work with George Li and Jason Li.
Presented as part of the Theory Lunch Seminar
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement
For More Information:
gzli@andrew.cmu.edu | matthewstewart@cmu.edu