DIMACS Theoretical Computer Science Seminar

Title: On the Complexity of the Graph Reachability Problem

Speaker: Vinodchandran Variyam, University of Nebraska-Lincoln

Date: Wednesday, April 25, 2012 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


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 present some progress we have made over the past 5 years at UNL on certain central open questions regarding the complexity of the reachability problem.

See: http://paul.rutgers.edu/~yixinxu/theory-spring12.html