Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-129 | 24th July 2018 22:21

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

RSS-Feed




Revision #1
Authors: Jelani Nelson, Huacheng Yu
Accepted on: 24th July 2018 22:21
Downloads: 55
Keywords: 


Abstract:

We show optimal lower bounds for spanning forest computation in two different models:

* One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the data structure should successfully answer with some given (potentially small) constant probability $\epsilon>0$. We prove that any such data structure must use $\Omega(n\log^3 n)$ bits of memory.

* There is a referee and $n$ vertices in a network sharing public randomness, and each vertex knows only its neighborhood; the referee receives no input. The vertices each send a message to the referee who then computes a spanning forest of the graph with constant probability $\epsilon>0$. We prove the average message length must be $\Omega(\log^3 n)$ bits.

Both our lower bounds are optimal, with matching upper bounds provided by the AGM sketch \cite{AhnGM12} (which even succeeds with probability $1 - 1/\mathrm{poly}(n)$). Furthermore, for the first setting we show optimal lower bounds even for low failure probability $\delta$, as long as $\delta > 2^{-n^{1-\epsilon}}$.



Changes to previous version:

The proof of Lemma 3 in version 1 was incorrect. We have replaced it with a slightly different statement, as well as modifying Lemma 5 to fit in with our new Lemma 3. Our final results are unchanged.


Paper:

TR18-129 | 13th July 2018 00:46

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation





TR18-129
Authors: Jelani Nelson, Huacheng Yu
Publication: 13th July 2018 17:41
Downloads: 135
Keywords: 


Abstract:

We show optimal lower bounds for spanning forest computation in two different models:

* One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the data structure should successfully answer with some given (potentially small) constant probability $\epsilon>0$. We prove that any such data structure must use $\Omega(n\log^3 n)$ bits of memory.

* There is a referee and $n$ vertices in a network sharing public randomness, and each vertex knows only its neighborhood; the referee receives no input. The vertices each send a message to the referee who then computes a spanning forest of the graph with constant probability $\epsilon>0$. We prove the average message length must be $\Omega(\log^3 n)$ bits.

Both our lower bounds are optimal, with matching upper bounds provided by the AGM sketch \cite{AhnGM12} (which even succeeds with probability $1 - 1/\mathrm{poly}(n)$). Furthermore, for the first setting we show optimal lower bounds even for low failure probability $\delta$, as long as $\delta > 2^{-n^{1-\epsilon}}$.



ISSN 1433-8092 | Imprint