Abstract

I will revisit the problem of determining the space complexity of arguably the oldest problem in streaming: count the number of ones in a data stream approximately. This work is joint with Miklos Ajtai.

Video Recording