What Can't We Compute on Data Streams?

Speaker  Amit Chakrabarti

Host  Milan Vojnovic

Affiliation  Dartmouth

Duration  00:29:50

Date recorded  24 May 2013

I will survey---at a very high level---the landscape of known space lower bounds for data stream computation and the crucial ideas, mostly from communication complexity, used to obtain these bounds. The survey will necessarily be biased towards results that I consider to be the best broad introduction. Later, I will outline a few basic problems where tight lower bounds are not known yet, so that improvements to known algorithms are possible.

©2013 Microsoft Corporation. All rights reserved.
> What Can't We Compute on Data Streams?