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\in [n]$$

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)$$

O

(

log

n

)

parties with high probability), then

$$\varOmega (n \min (\log 1/\delta , \log k) / k )$$

Ω

(

n

min

(

log

1

/

δ

,

log

k

)

/

k

)

communication is required by any

$$\delta $$

δ

-error communication protocol for this problem (assuming

$$k = \varOmega (\log n)$$

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

$$\varOmega (n^{1-2/p} \varepsilon ^{-2} \log M \log 1/\delta )$$

Ω

(

n

1

-

2

/

p

ε

-

2

log

M

log

1

/

δ

)

bits for any algorithm giving a

$$(1+\varepsilon )$$

(

1

+

ε

)

-approximation to the

p

-th moment

$$\sum _{i=1}^n |x_i|^p$$

∑

i

=

1

n

|

x

i

|

p

of an

n

-dimensional vector

$$x\in \{\pm M\}^n$$

x

∈

{

±

M

}

n

with probability

$$1-\delta $$

1

-

δ

, for any

$$\delta \ge 2^{-o(n^{1/p})}$$

δ

≥

2

-

o

(

n

1

/

p

)

. Our lower bound improves upon a prior

$$\varOmega (n^{1-2/p} \varepsilon ^{-2} \log M)$$

Ω

(

n

1

-

2

/

p

ε

-

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)$$

ε

≤

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.