
CS Colloquium
Thu, Apr 21, 2011 @ 03:30 PM  05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Subhash Suri, UCSB
Talk Title: Paths, Trees and Polygons
Abstract: The growing scope of combinatorial algorithms often forces us to compute structures when the data are incomplete, uncertain, or timevarying. In this talk, we revisit three classical problems (Shortest Paths, Minimum Spanning Trees, and Polygon Guarding) under such informational and sensing models, and derive new complexity bounds or impossibility results.
In particular, we show that
(1) if the travel times for the edges of a graph are a (polynomial) functions of time, there can be superpolynomial number of shortest paths between two nodes,
(2) if each of the $n$ points in the plane is present only probabilistically, computing the expected length of their minimum spanning tree is intractable, and
(3) many basic geometric problems such as the Art Gallery coverage of a polygon can be solved in a "binary combinatorial sensing model" that does not require knowledge of coordinates.
Biography: Subhash Suri received his Ph.D. in Computer Science from Johns Hopkins University in 1987 and B.S. in Electronics Engineering from University Of Roorkee, India in 1981. His research interests are in Algorithms, Wireless Sensor Networks, Data Streams, Computational Geometry, and Game Theory. For more information, see http://www.cs.ucsb.edu/~suri/
Host: Prof. Gaurav Sukhatme
Location: Seaver Science Library (SSL)  150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal