Skip to main content

The Coin Problem with Applications to Data Streams

Author(s): Braverman, Mark; Garg, Sumegha; Woodruff, David P

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr16v75
Abstract: Consider the problem of computing the majority of a stream of n i.i.d. uniformly random bits. This problem, known as the coin problem, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant advantage must use Ω(log n) bits of space. We extend our lower bound to proving tight lower bounds for solving multiple, randomly interleaved copies of the coin problem, as well as for solving the OR of multiple copies of a variant of the coin problem. Our proofs involve new measures of information complexity that are well-suited for data streams. We use these lower bounds to obtain a number of new results for data streams. In each case there is an underlying d dimensional vector x with additive updates to its coordinates given in a stream of length m. The input streams arising from our coin lower bound have nice distributional properties, and consequently for many problems for which we only had lower bounds in general turnstile streams, we now obtain the same lower bounds in more natural models, such as the bounded deletion model, in which ||x|| 2 never drops by a constant fraction of what it was earlier, or in the random order model, in which the updates are ordered randomly. In particular, in the bounded deletion model, we obtain nearly tight lower bounds for approximating ||x|| ∞ up to additive error [1/(√k)]||x|| 2 , approximating ||x|| 2 up to a multiplicative ( 1+ε) factor (resolving a question of Jayaram and Woodruff in PODS 2018), and solving the Point Query and ℓ 2 -Heavy Hitters Problems. In the random order model, we also obtain new lower bounds for the Point Query and ℓ 2 -Heavy Hitters Problems. We also give new algorithms complementing our lower bounds and illustrating the tightness of the models we consider, including an algorithm for approximating ||x|| ∞ up to additive error [1/(√k)]||x||2 in turnstile streams (resolving a question of Cormode in a 2006 IITK Workshop), and an algorithm for finding ℓ 2 -heavy hitters in randomly ordered insertion streams (which for random order streams, resolves a question of Nelson in a 2018 Warwick Workshop).
Publication Date: 2020
Citation: Braverman, Mark, Sumegha Garg, and David P. Woodruff. "The Coin Problem with Applications to Data Streams." In IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) (2020): pp. 318-329. doi:10.1109/FOCS46700.2020.00038
DOI: 10.1109/FOCS46700.2020.00038
ISSN: 1523-8288
EISSN: 2575-8454
Pages: 318 - 329
Type of Material: Conference Article
Journal/Proceeding Title: IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.