The Simultaneous Communication of Disjointness with Applications to Data Streams

摘要

We study k-party number-in-hand set disjointness in the simultaneous message-passing model, and show that even if each element i ∈ [n] is guaranteed to either belong to all k parties or to at most O(1) parties in expectation (and to at most O(logrn) parties with high probability), then Ω(nmin(log 1/δ,logk)/k) communication is required by any δ-error communication protocol for this problem (assuming k = Ω(logn)). 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 Ω(n~(1-2/p_ε-2)logMlogl/δ) bits for any algorithm giving a (1 + ε)-approximation to the p-th moment ∑_(i=1)~n=1|x_i|~p of an n-dimensional vector x ∈ {±M}~n with probability 1 - δ, for any δ ≥ 2~(-o(n~1/p)). Our lower bound improves upon a prior Ω(n~(1-2/p_ε-2)log M) lower bound which did not capture the dependence on 5, and our bound is optimal whenever ε ≤1/poly(logn). 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.