Connectivity and electricity
Kent Quanrud · 77:19
This lecture shows that undirected \(s\)-\(t\) connectivity can be solved in logarithmic space by a random walk, and proves it by a detour through electrical networks: commute hitting times equal \(2m\) times unit eff...