### 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

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 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