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

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