We study k -party 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 ( log n ) parties with high probability), then ( n min ( log 1 log k ) k ) communication is required by any -error communication protocol for this problem (assuming k = ( 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 ( n 1 − 2 p − 2 log M log 1 ) bits for any algorithm giving a (1 + ) -approximation to the p -th moment n i =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 , and our bound is optimal whenever 1 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.