[Colloq] REMINDER: Today, 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

_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq