## 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 > 0. We prove that any such data structure must use Ω(nlog^{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 > 0. We prove the average message length must be Ω(log^{3} n) bits. Both our lower bounds are optimal, with matching upper bounds provided by the AGM sketch [AGM12] (which even succeeds with probability 1 − 1/poly(n)). Furthermore, for the first setting we show optimal lower bounds even for low failure proba-1− bility δ, as long as δ > 2^{−}n .

Original language | English (US) |
---|---|

Pages | 1844-1860 |

Number of pages | 17 |

DOIs | |

State | Published - 2019 |

Externally published | Yes |

Event | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States Duration: Jan 6 2019 → Jan 9 2019 |

### Conference

Conference | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 |
---|---|

Country/Territory | United States |

City | San Diego |

Period | 1/6/19 → 1/9/19 |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)