English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the semi-streaming model for processing massive graphs, an algorithm makesmultiple passes over the edges of a given $n$-vertex graph and is tasked withcomputing the solution to a problem using $O(n \cdot \text{polylog}(n))$ space.Semi-streaming algorithms for Maximal Independent Set (MIS) that run in$O(\log\log{n})$ passes have been known for almost a decade, however, the bestlower bounds can only rule out single-pass algorithms. We close this large gapby proving that the current algorithms are optimal: Any semi-streamingalgorithm for finding an MIS with constant probability of success requires$\Omega(\log\log{n})$ passes. This settles the complexity of this fundamentalproblem in the semi-streaming model, and constitutes one of the first optimalmulti-pass lower bounds in this model.  We establish our result by proving an optimal round vs communication tradeofffor the (multi-party) communication complexity of MIS. The key ingredient ofthis result is a new technique, called hierarchical embedding, for performinground elimination: we show how to pack many but small hard $(r-1)$-roundinstances of the problem into a single $r$-round instance, in a way thatenforces any $r$-round protocol to effectively solve all these $(r-1)$-roundinstances also. These embeddings are obtained via a novel application ofresults from extremal graph theory -- in particular dense graphs with manydisjoint unique shortest paths -- together with a newly designed graph product,and are analyzed via information-theoretic tools such as direct-sum and messagecompression arguments.

$\mathcal{O}(\log\log{n})$ Passes is Optimal for Semi-Streaming Maximal Independent Set