Events - Colloquia & Seminars

CCIS Colloquium Spring 2007

On the Space Complexity of Directed Planar Reachability Problem

Speaker: Vinodchandran Variyam

Affiliation: University of Nebraska-Lincoln

Date: Monday, May 7, 2007

Talk: 12:00 p.m. - 1:00 p.m., 366 WVH

Abstract

Graph reachability problems are fundamental to the study of space bounded computations. Reachability problem for general directed graphs (given a directed graph G and two vertices s and t, is t reachable from s?) characterizes the complexity of computational problems solvable using non-deterministic machines with logarithmic space bound. A recent breakthrough result due to Reingold implies that the reachability problem for undirected graphs captures all of deterministic logarithmic space bounded computations. Various restricted versions of reachability problem are known to characterize other small-space complexity classes.

In this talk we look at the space complexity of directed planar graph reachability problem. Planar graphs are an important and natural subclass of general graphs and are well studied in graph theory. However, the space complexity of reachability problem for directed planar graphs is not yet well understood. We make progress on this situation by giving a new upper bound on its space complexity. This is a joint work with Chris Bourke and Raghunath Tewari.

Brief Biography

Vinodchandran Variyam is an Assistant Professor at the University of Nebraska-Lincoln since September 2001. Before joining UNL, he served as a Research Assistant Professor at the University of Aarhus, Denmark, and as a postdoctoral fellow at NEC research Institute, Princeton. He received his PhD from the Institute of Mathematical Sciences, Chennai, India. Prof. Variyam conducts research in the area of computational complexity theory. He has made original contributions in several closely related topics in complexity theory including derandomization, circuit complexity, space bounded complexity classes, complexity of intermediate problems, Kolmogorov complexity, and average-case complexity.