Simons Institute | O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set @SimonsInstituteTOC | Uploaded 1 week ago | Updated 18 hours ago
Sepehr Assadi (University of Waterloo)
https://simons.berkeley.edu/talks/sepehr-assadi-university-waterloo-2024-08-07
Workshop on Local Algorithms (WoLA)
How far can more recent models of computation go beyond classical locality bounds? We study this question in the context of the maximal independent set (MIS) problem and the semi-streaming model. In this model, an algorithm makes multiple passes over the edges of a given n-vertex graph presented in an arbitrarily-ordered stream and is tasked with computing the solution to a problem using O(n⋅polylog(n)) space.
There is an easy O(log n) randomized pass algorithm for computing MIS in the semi-streaming model by directly simulating classical LOCAL algorithms for this problem. It was also known since almost a decade ago that one can exponentially speedup essentially the same LOCAL algorithm and achieve an O(log log n) pass algorithm. This approach has since formed the backbone of several other "round compression" results for exponentially speeding up LOCAL algorithms for different problems across various other models as well.
In this talk, we present a new lower bound, showing that one cannot go beyond this exponential speedup: Any semi-streaming algorithm for finding an MIS with constant probability of success requires Ω(log log n) passes. The proof introduces a new a family of extremal graphs that generalize so-called Ruzsa-Szemeredi graphs and a new round elimination technique for proving communication and space complexity lower bounds in the context of semi-streaming algorithms.
Based on joint work with Christian Konrad, Kheeran Naidu, and Janani Sundaresan: arxiv.org/pdf/2312.13178.pdf
Sepehr Assadi (University of Waterloo)
https://simons.berkeley.edu/talks/sepehr-assadi-university-waterloo-2024-08-07
Workshop on Local Algorithms (WoLA)
How far can more recent models of computation go beyond classical locality bounds? We study this question in the context of the maximal independent set (MIS) problem and the semi-streaming model. In this model, an algorithm makes multiple passes over the edges of a given n-vertex graph presented in an arbitrarily-ordered stream and is tasked with computing the solution to a problem using O(n⋅polylog(n)) space.
There is an easy O(log n) randomized pass algorithm for computing MIS in the semi-streaming model by directly simulating classical LOCAL algorithms for this problem. It was also known since almost a decade ago that one can exponentially speedup essentially the same LOCAL algorithm and achieve an O(log log n) pass algorithm. This approach has since formed the backbone of several other "round compression" results for exponentially speeding up LOCAL algorithms for different problems across various other models as well.
In this talk, we present a new lower bound, showing that one cannot go beyond this exponential speedup: Any semi-streaming algorithm for finding an MIS with constant probability of success requires Ω(log log n) passes. The proof introduces a new a family of extremal graphs that generalize so-called Ruzsa-Szemeredi graphs and a new round elimination technique for proving communication and space complexity lower bounds in the context of semi-streaming algorithms.
Based on joint work with Christian Konrad, Kheeran Naidu, and Janani Sundaresan: arxiv.org/pdf/2312.13178.pdf
