Title:  Graph Problems in the Streaming Model 
Speaker: Sampath Kannan
UPenn
Date: Wednesday, October 11, 2006
Time 2-3PM
Venue: Room 3464 (Math/CS Conference Room)  HKUST

  
Abstract:
We describe a recent model of computation called the streaming model. 
This model captures the increasingly common situation where the 
volume of data processed by a computer is much larger than what 
will fit in memory. An added restriction is that the computer is 
required to process each data item in "real time". We provide 
positive and negative results on the existence of algorithms 
for some classical graph problems such as matching and computing 
distances in this model.

(joint work with J. Feigenbaum, A. McGregor, S. Suri, and J. Zhang)

Bio.  Sampath Kannan is a Professor of Computer and Information Science 
at the University of Pennsylvania.