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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Detection of a planted dense subgraph in a random graph is a fundamentalstatistical and computational problem that has been extensively studied inrecent years. We study a hypergraph version of the problem. Let $G^r(n,p)$denote the $r$-uniform Erd\H{o}s-R\'enyi hypergraph model with $n$ vertices andedge density $p$. We consider detecting the presence of a planted$G^r(n^\gamma, n^{-\alpha})$ subhypergraph in a $G^r(n, n^{-\beta})$hypergraph, where $0< \alpha < \beta < r-1$ and $0 < \gamma < 1$. Focusing ontests that are degree-$n^{o(1)}$ polynomials of the entries of the adjacencytensor, we determine the threshold between the easy and hard regimes for thedetection problem. More precisely, for $0 < \gamma < 1/2$, the threshold isgiven by $\alpha = \beta \gamma$, and for $1/2 \le \gamma < 1$, the thresholdis given by $\alpha = \beta/2 + r(\gamma - 1/2)$.  Our results are already new in the graph case $r=2$, as we consider thesubtle log-density regime where hardness based on average-case reductions isnot known. Our proof of low-degree hardness is based on a conditional variantof the standard low-degree likelihood calculation.

Detection of Dense Subhypergraphs by Low-Degree Polynomials