Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms

EADS Talk by Kasper Green Larsen, Aarhus University


We say a turnstile streaming algorithm is non-adaptive if, during updates, the memory cells written and read depend only on the index being updated and random coins tossed at the beginning of the stream (and not on the memory contents of the algorithm). Memory cells read during queries may be decided upon adaptively. All known turnstile streaming algorithms in the literature are non-adaptive. In fact, even more specifically, they are all linear sketches. 

We prove the first non-trivial update time lower bounds for both randomized and deterministic turnstile streaming algorithms, which hold when the algorithms are non-adaptive. While there has been abundant success in proving space lower bounds, there have been no non-trivial turnstile update time lower bounds. Our lower bounds hold against classically studied problems such as heavy hitters, point query, entropy estimation, and moment estimation. In some cases of deterministic algorithms, our lower bounds nearly match known upper bounds.

Joint work with: Jelani Nelson (Harvard) and Huy L. Nguyen (TTIC)

Short Bio of Kasper Green Larsen

Assistant Professor, PhD at MADALGO (Centre for Massive Data Algorithmics) at the Department of Computer Science, Aarhus University. His main research area is data structures with an emphasis on range searching and lower bounds.

More info on research and projects