[Colloq] May 7 - Vinodchandran Variyam - “On the Space Complexity of Directed Planar Reachability Problem”

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Vinodchandran Variyam
University of Nebraska-Lincoln

Who will speak on:
“On the Space Complexity of Directed Planar Reachability Problem”

Monday, May 7, 2007
12:00 pm
366 West Village H
Northeastern University


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.

Host: Ravi Sundaram