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 first present certain significant open problems regarding the complexity of the reachability problem and then describe the progress we (specifically Chris Bourke, Raghu Tewari, Derrick Stolee and I) have made over the past 5 years at UNL towards solving them.
Speaker Biography
Vinodchandran Variyam is an Associate Professor and Susan Rosowski Professor at the University of Nebraska-Lincoln. Before joining UNL in 2001, he served as a postdoctoral fellow at NEC research Institute, Princeton, and earlier as a Research Assistant Professor at the University of Aarhus, Denmark. He received his PhD from the Institute of Mathematical Sciences, Chennai, India. Prof. Variyam conducts research in computational complexity theory. He has made significant contributions in several topics in complexity theory including space bounded computations, derandomization, circuit complexity, complexity of intermediate problems, Kolmogorov complexity, and average-case complexity.