Speaker: Sampath Kannan University of Pennsylvania
Time: 2006-10-19 14:00-2006-10-19 15:00
Venue: FIT Building,Tsinghua University
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)
Short Bio:
