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 aim to understand the extent to which the noise distribution in a plantedsignal-plus-noise problem impacts its computational complexity. To that end, weconsider the planted clique and planted dense subgraph problems, but in adifferent ambient graph. Instead of Erd\H{o}s-R\'enyi $G(n,p)$, which hasindependent edges, we take the ambient graph to be the random graph withtriangles (RGT) obtained by adding triangles to $G(n,p)$. We show that the RGTcan be efficiently mapped to the corresponding $G(n,p)$, and moreover, that theplanted clique (or dense subgraph) is approximately preserved under thismapping. This constitutes the first average-case reduction transformingdependent noise to independent noise. Together with the easier direction ofmapping the ambient graph from Erd\H{o}s-R\'enyi to RGT, our results yield astrong equivalence between models. In order to prove our results, we develop anew general framework for reasoning about the validity of average-casereductions based on low sensitivity to perturbations.

Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles