Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
Learn about the optimal pass complexity for computing maximal independent sets in the semi-streaming model through this 46-minute conference talk that establishes O(log log n) passes as the precise threshold for this fundamental graph problem. Explore the theoretical foundations and proof techniques that demonstrate why O(log log n) passes are both necessary and sufficient for finding maximal independent sets when processing graphs in a streaming fashion with limited memory. Discover the implications of this result for streaming algorithms and understand how this optimal bound connects to broader questions in computational complexity theory. Examine the mathematical framework used to prove both the upper and lower bounds, including the construction of hard instances that require at least O(log log n) passes and the algorithmic techniques that achieve this bound. Gain insights into semi-streaming algorithms, where the available memory is sublinear in the input size but larger than the logarithmic space typically assumed in streaming models.
