Manage Events
All events are in Central time unless specified.
Colloquium

Mathematics Colloquium

Date:
Time:
4:00 pm – 4:50 pm
Avery Hall Room: 115
1144 T St
 Lincoln NE 68508
Additional Info: AVH
Speaker: Vinodchandran Variyam
Affiliation: Department of Computer Science and Engineering, University of Nebraska
Local Host: Steve Cohn
Title: Space Complexity of The Directed Graph Reachability Problem

Additional Public Info:
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 on certain central open questions regarding the space complexity of the reachability problem.

Refreshments will be served 3:30-4:00 in 348 Avery. The talk is free and open to the public.

Download this event to my calendar

This event originated in Math Colloquia.