Fwd: Expert Lecture - Graph Reachibility - CSED - Today 3:30 PM ELHC 203.

1 view

Skip to first unread message

Kartik Singhal

unread,

Jul 23, 2012, 3:04:04 AM7/23/12

to CSE09 Batch BTech NITC

---------- Forwarded message ----------
From: Murali Krishnan <kmu...@nitc.ac.in>
Date: Mon, Jul 23, 2012 at 9:57 AM
Subject: Expert Lecture - Graph Reachibility - CSED - Today 3:30 PM ELHC 203.
To: "Computer Science and Engineering 2008 Batch(B.tech)" <bc...@nitc.ac.in>, bcs09 <bc...@nitc.ac.in>, mca09 <mc...@nitc.ac.in>, mcs10 <mc...@nitc.ac.in>, mcssecurity <mcss...@nitc.ac.in>

Speaker: Prof. Vinodchandran N. Variyam,
Associate Professor and Susan Rosowski Professor,
Department of Computer Sc. and Engg.,
University of Nebraska, Lincoln.
http://cse.unl.edu/~vinod/
(The speaker is an alumnus of NIT Calicut.).

> ABSTRACT (as received from the speaker)

> 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 over the past
> few years at UNL on certain central open questions regarding the
> complexity of the reachability problem.
>

Schedule : Monday, July 23, 3:30 PM, ELHC 203.

Kindly pass this information to interested students in your department.