Combinatorics Seminar
A crash course in complexity theory
Anurag Sahay (University of Rochester)
Tuesday, February 25th, 2020
11:00 AM - 12:00 PM
Hylan 1106A
11:00 AM - 12:00 PM
Hylan 1106A
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
Add to Google Calendar