February 17, 2011 - Vinodchandran Variyam

Title: On the Complexity of The Graph Reachability Problem

Abstract:
The graph reachability problem, the computational problem of deciding whether there is a path between two given vertices in a graph, is the canonical problem while studying space bounded computations.
Different variations of this problem characterize various important space bounded complexity classes. In particular it is a basic fact that, over directed graphs, this problem completely characterizes non-deterministic logarithmic space bounded computations. Understanding the complexity of the reachability problem is a central concern of computational complexity theory.

In this talk I will first present certain significant open problems regarding the complexity of the reachability problem and then describe the progress we (specifically Chris Bourke, Raghu Tewari, Derrick Stolee and I) have made over the past 5 years at UNL towards solving them.