Deterministic connectivity with logarithmic space
Kent Quanrud · 75:22
This lecture shows how to derandomize undirected \(s\)-\(t\) connectivity into deterministic log space: first solve the special case of constant-degree expanders by enumerating all \(\log n\)-step walks, then implicit...