## Abstract

The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over dynamic streams with both insertions and deletions of edges. This includes algorithms for cut sparsification, spanners, matchings, and minimum spanning trees (MSTs). These results have since been improved or generalized in various directions, leading to a vastly rich host of efficient algorithms for processing dynamic graph streams. A curious omission from the list of improvements has been the MST problem. The best algorithm for this problem remains the original AGM algorithm that for every integer p ≥ 1, uses n^{1+O(1/p)} space in p passes on n-vertex graphs, and thus achieves the desired semi-streaming space of Õ(n) at a relatively high cost of O(logn/loglogn) passes. On the other hand, no lower bound beyond a folklore one-pass lower bound is known for this problem. We provide a simple explanation for this lack of improvements: The AGM algorithm for MSTs is optimal for the entire range of its number of passes! We prove that even for the simplest decision version of the problem - deciding whether the weight of MSTs is at least a given threshold or not - any p-pass dynamic streaming algorithm requires n^{1+Ω(1/p)} space. This implies that semi-streaming algorithms do need Ω(logn/loglogn) passes. Our result relies on proving new multi-round communication complexity lower bounds for a variant of the universal relation problem that has been instrumental in proving prior lower bounds for single-pass dynamic streaming algorithms. The proof also involves proving new composition theorems in communication complexity, including majority lemmas and multi-party XOR lemmas, via information complexity approaches.

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

Title of host publication | STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing |

Editors | Bojan Mohar, Igor Shinkar, Ryan O�Donnell |

Publisher | Association for Computing Machinery |

Pages | 835-846 |

Number of pages | 12 |

ISBN (Electronic) | 9798400703836 |

DOIs | |

State | Published - Jun 10 2024 |

Event | 56th Annual ACM Symposium on Theory of Computing, STOC 2024 - Vancouver, Canada Duration: Jun 24 2024 → Jun 28 2024 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 56th Annual ACM Symposium on Theory of Computing, STOC 2024 |
---|---|

Country/Territory | Canada |

City | Vancouver |

Period | 6/24/24 → 6/28/24 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Communication complexity
- Minimum spanning trees
- Streaming algorithm