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 .
If time permits, we will sketch why directed graph connectivity is NL-complete, and sketch a proof of Savitch’s theorem that .
Event contact: hazel dot mcknight at rochester dot edu