Fall 2018

On the Deterministic Complexity of Counting Events in a Stream

Thursday, October 18th, 2018 11:00 am11:30 am

Add to Calendar


T.S. Jayram (IBM Almaden)

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.