Optimal Multi-pass Lower Bounds for MST in Dynamic Streams

Sepehr Assadi, Gillat Kol, Zhijun Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 n1+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 n1+Ω(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 languageEnglish (US)
Title of host publicationSTOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing
EditorsBojan Mohar, Igor Shinkar, Ryan O�Donnell
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Electronic)9798400703836
StatePublished - Jun 10 2024
Event56th Annual ACM Symposium on Theory of Computing, STOC 2024 - Vancouver, Canada
Duration: Jun 24 2024Jun 28 2024

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Conference56th Annual ACM Symposium on Theory of Computing, STOC 2024

All Science Journal Classification (ASJC) codes

  • Software


  • Communication complexity
  • Minimum spanning trees
  • Streaming algorithm


Dive into the research topics of 'Optimal Multi-pass Lower Bounds for MST in Dynamic Streams'. Together they form a unique fingerprint.

Cite this