Faster Algorithms and New Iterative Methods for Computing the Stationary Distribution

Explore advanced techniques for computing stationary distributions in directed graphs through this lecture by Aaron Sidford from Stanford University. Delve into faster algorithms and new iterative methods, including the Laplacian paradigm and Eulerian scaling algorithm. Learn about applications of Laplacian solvers, the importance of directed graphs, and the state-of-the-art in this field. Gain insights into undirected graph sparsification and understand why reducing to Eulerian graphs is beneficial. This talk, part of the "Fast Iterative Methods in Optimization" series at the Simons Institute, offers a comprehensive overview of cutting-edge research in graph algorithms and optimization techniques.

Intro
Michael B. Cohen
The Problem
Why This Workshop?
Laplacian Solver Applications
What About Directed Graphs?
Directed? "The Laplacian Paradigm"
What is the state of the art?
How? - Second Paper
Why Want Eulerian?
Why Can Reduce to Eulerian?
Eulerian Scaling Algorithm
Undirected Graph Sparsification