__
TR16-111 | 20th July 2016 05:37
__

#### Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics

**Abstract:**
We develop a paradigm for studying multi-player deterministic communication,

based on a novel combinatorial concept that we call a {\em strong fooling

set}. Our paradigm leads to optimal lower bounds on the per-player

communication required for solving multi-player $\textsc{equality}$

problems in a private-message setting. This in turn gives a very strong---$O(1)$

versus $\Omega(n)$---separation between private-message and one-way blackboard

communication complexities.

Applying our communication complexity results, we show that for deterministic

data streaming algorithms, even loose estimations of some basic statistics of an

input stream require large amounts of space. For instance, approximating the

frequency moment $F_k$ within a factor $\alpha$ requires

$\Omega(n/\alpha^{1/(1-k)})$ space for $k 1$. In particular, approximation

within any {\em constant} factor $\alpha$, however large, requires {\em linear}

space, with the trivial exception of $k = 1$. This is in sharp contrast to the

situation for randomized streaming algorithms, which can approximate $F_k$ to

within $(1\pm\varepsilon)$ factors using $\widetilde{O}(1)$ space for $k \le 2$

and $o(n)$ space for all finite $k$ and all constant $\varepsilon > 0$. Previous

linear-space lower bounds for deterministic estimation were limited to small

factors $\alpha$, such as $\alpha < 2$ for approximating $F_0$ or $F_2$.

We also provide certain space/approximation tradeoffs in a deterministic setting

for the problems of estimating the empirical entropy of a stream as well as the

size of the maximum matching and the edge connectivity of a streamed graph.