Events Calendar

CS Colloquium

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 time-varying. 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 super-polynomial 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