Tata Institute of Fundamental Research
Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics
STCS Seminar
Speaker:
Sagar Kale (Dartmouth College
Department of Computer Science
6211 Sudikoff Lab
Hanover, NH-03755-3510
United States of America)
Organiser:
Arkadev Chattopadhyay
Date:
Tuesday, 6 Dec 2016, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
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 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$ and roughly $\Omega(n/\alpha^{k/(k-1)})$ 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 (this is joint work with Amit Chakrabarti).
| Speaker: | Sagar Kale (Dartmouth College Department of Computer Science 6211 Sudikoff Lab Hanover, NH-03755-3510 United States of America) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Tuesday, 6 Dec 2016, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
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 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$ and roughly $\Omega(n/\alpha^{k/(k-1)})$ 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 (this is joint work with Amit Chakrabarti).
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$ and roughly $\Omega(n/\alpha^{k/(k-1)})$ 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 (this is joint work with Amit Chakrabarti).