Completed
Derandomization via Laplacian solvers
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
High-Precision Estimation of Random Walks in Small Space
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 RL vs. L via Pseudorandom Generators
- 3 RL vs. L via Graph Algorithms
- 4 Directed Graphs
- 5 Directed Laplacians Def: The Laplacian of G is L=1-W.
- 6 Solving Laplacian systems Lx = b
- 7 Application: Deterministic Algorithms for ERWP
- 8 ERWP via Laplacians: the Eulerian case
- 9 ERWP Algorithm Outline
- 10 Unit Circle Approximation Definition of Approximation for Laplacian Matrices
- 11 Derandomization via Laplacian solvers
- 12 Open problems and future directions
