Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms

DSpace/Manakin Repository

Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms

Citable link to this page


Title: Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
Author: Larsen, Kasper Green; Nelson, Jelani; Nguyen, Huy L.

Note: Order does not necessarily reflect citation order of authors.

Citation: Larsen, Kasper Green, Jelani Nelson, and Huy L. Nguyen. 2014. "Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms." In Proceedings of the forty-seventh annual ACM symposium on Theory of computing (STOC 15), Portland, OR, June 14-17, 2015: 803-812. doi: 10.1145/2746539.2746542
Full Text & Related Files:
Abstract: 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. 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 update time lower bounds in the turnstile model. 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.
Published Version: 10.1145/2746539.2746542
Other Sources: http://arxiv.org/abs/1407.2151
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAP
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:34305996
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search