The Simultaneous Communication of Disjointness with Applications to Data Streams
Lists
Only you see this
Abstract
We study k-party number-in-hand set disjointness in the simultaneous message-passing model, and show that even if each element $$i\in [n]$$ is guaranteed to either belong to all k parties or to at most O(1) parties in expectation (and to at most $$O(\log n)$$ parties with high probability), then $$\varOmega (n \min (\log 1/\delta , \log k) / k )$$ communication is required by any $$\delta $$ -error communication protocol for this problem (assuming $$k = \varOmega (\log n)$$ ). We use the strong promise of our lower bound, together with a recent characterization of turnstile streaming algorithms as linear sketches, to obtain new lower bounds for the well-studied problem in data streams of approximating the frequency moments. We obtain a space lower bound of $$\varOmega (n^{1-2/p} \varepsilon ^{-2} \log M \log 1/\delta )$$ bits for any algorithm giving a $$(1+\varepsilon )$$ -approximation to the p-th moment $$\sum _{i=1}^n |x_i|^p$$ of an n-dimensional vector $$x\in \{\pm M\}^n$$ with probability $$1-\delta $$ , for any $$\delta \ge 2^{-o(n^{1/p})}$$ . Our lower bound improves upon a prior $$\varOmega (n^{1-2/p} \varepsilon ^{-2} \log M)$$ lower bound which did not capture the dependence on $$\delta $$ , and our bound is optimal whenever $$\varepsilon \le 1/\text {poly}(\log n)$$ . This is the first example of a lower bound in data streams which uses a characterization in terms of linear sketches to obtain stronger lower bounds than obtainable via the one-way communication model; indeed, our set disjointness lower bound provably cannot hold in the one-way model.
BibTeX
@inproceedings{weinstein2015simultaneous,
author = {Omri Weinstein and David P. Woodruff},
title = {{The Simultaneous Communication of Disjointness with Applications to Data Streams}},
booktitle = {ICALP},
year = {2015},
doi = {10.1007/978-3-662-47672-7\_88},
}Loading related content...