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/

Zendy Plus

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

Zendy Tools

Zendy Open

By far the most fruitful technique for showing lower bounds for the CONGESTmodel is reductions to two-party communication complexity. This technique hasyielded nearly tight results for various fundamental problems such as distancecomputations, minimum spanning tree, minimum vertex cover, and more.  In this work, we take this technique a step further, and we introduce aframework of reductions to $t$-party communication complexity, for every $t\geq2$. Our framework enables us to show improved hardness results for maximumindependent set. Recently, Bachrach et al.[PODC 2019] used the two-partyframework to show hardness of approximation for maximum independent set. Theyshow that finding a $(5/6+\epsilon)$-approximation requires $\Omega(n/\log^6n)$ rounds, and finding a $(7/8+\epsilon)$-approximation requires$\Omega(n^2/\log^7 n)$ rounds, in the CONGEST model where $n$ in the number ofnodes in the network.  We improve the results of Bachrach et al. by using reductions to multi-partycommunication complexity. Our results:  (1) Any algorithm that finds a $(1/2+\epsilon)$-approximation for maximumindependent set in the CONGEST model requires $\Omega(n/\log^3 n)$ rounds.  (2) Any algorithm that finds a $(3/4+\epsilon)$-approximation for maximumindependent set in the CONGEST model requires $\Omega(n^2/\log^3 n)$ rounds.

Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST