Anurag Sahay (University of Rochester)
11:00 AM - 12:00 PM
We will review the basics of computational complexity, with a view towards understanding the significance of Reingold’s theorem that undirected graph connectivity is in \(L\).
If time permits, we will sketch why directed graph connectivity is NL-complete, and sketch a proof of Savitch’s theorem that \(NL \subseteq L^2\).
Event contact: hazel dot mcknight at rochester dot edu