We study `space-pass tradeoffs' for computing maximal independent sets through the lens of semi-streaming algorithms. In the semi-streaming model, an algorithm makes multiple passes over the edges of a given n-vertex graph and is tasked with computing the solution to a problem using O(n⋅polylog(n)) space. How many passes are needed for computing any (arbitrary) maximal independent set in a given graph?

While semi-streaming algorithms for Maximal Independent Set (MIS) that run in O(log log n) passes have been known for over a decade now, the best lower bounds can only rule out single-pass algorithms. We close this large gap by proving that the current algorithms are optimal: any semi-streaming algorithm for finding an MIS with constant probability of success requires Ω(log log n) passes. The proof introduces a new construction of a family of extremal graphs that generalize the so-called Ruzsa-Szemeredi graphs and a new round elimination technique for proving communication complexity and space complexity lower bounds in the context of semi-streaming algorithms.

Based on joint work with Christian Konrad, Kheeran Naidu,and Janani Sundaresan.