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

We present the first super-linear lower bounds for natural graph problems inthe CONGEST model, answering a long-standing open question.  Specifically, we show that any exact computation of a minimum vertex cover ora maximum independent set requires $\Omega(n^2/\log^2{n})$ rounds in the worstcase in the CONGEST model, as well as any algorithm for $\chi$-coloring agraph, where $\chi$ is the chromatic number of the graph. We further show thatsuch strong lower bounds are not limited to NP-hard problems, by showing twosimple graph problems in P which require a quadratic and near-quadratic numberof rounds.  Finally, we address the problem of computing an exact solution to weightedall-pairs-shortest-paths (APSP), which arguably may be considered as acandidate for having a super-linear lower bound. We show a simple $\Omega(n)$lower bound for this problem, which implies a separation between the weightedand unweighted cases, since the latter is known to have a complexity of$\Theta(n/\log{n})$. We also formally prove that the standard Alice-Bobframework is incapable of providing a super-linear lower bound for exactweighted APSP, whose complexity remains an intriguing open question.

Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model