Time lower bounds for nonadaptive turnstile streaming algorithms

Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen

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…