Name
Title | ||
|---|---|---|
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. |
Abstract | ||
|---|---|---|
In a $k$-party communication problem, the $k$ players with inputs $x_1, x_2, \ldots, x_k$, respectively, want to evaluate a function $f(x_1, x_2, \ldots, x_k)$ using as little communication as possible. We consider the message-passing model, in which the inputs are partitioned in an arbitrary, possibly worst-case manner, among a smaller number $t$ of players ($t<k$). The $t$-player communication cost of computing $f$ can only be smaller than the $k$-player communication cost, since the $t$ players can trivially simulate the $k$-player protocol. But how much smaller can it be? We study deterministic and randomized protocols in the one-way model, and provide separations for product input distributions, which are optimal for low error probability protocols. We also provide much stronger separations when the input distribution is non-product. A key application of our results is in proving lower bounds for data stream algorithms. In particular, we give an optimal $\Omega(\varepsilon^{-2}\log(N) \log \log(mM))$ bits of space lower bound for the fundamental problem of $(1\pm\varepsilon)$-approximating the number $\|x\|_0$ of non-zero entries of an $n$-dimensional vector $x$ after $m$ updates each of magnitude $M$, and with success probability $\ge 2/3$, in a strict turnstile stream. Our result matches the best known upper bound when $\varepsilon\ge 1/\mathsf{polylog}(mM)$. It also improves on the prior $\Omega(\varepsilon^{-2}\log(mM) )$ lower bound and separates the complexity of approximating $L_0$ from approximating the $p$-norm $L_p$ for $p$ bounded away from $0$, since the latter has an $O(\varepsilon^{-2}\log (mM))$ bit upper bound. |
Year | Venue | Field |
|---|---|---|
2019 | ICALP | Magnitude (mathematics),Discrete mathematics,Data stream mining,Combinatorics,Data stream,Turnstile,Upper and lower bounds,Omega,Probability of error,Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1905.07135 | 1 |
PageRank | References | Authors |
0.35 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David P. Woodruff | 1 | 2156 | 142.38 |
| Guang Yang | 2 | 17 | 3.33 |