Average-Case Hardness of Hypergraphic Planted Clique Detection

§ Problem Statement

Setup

Fix an integer $d\ge 3$ and let $[N]=\{1,\dots,N\}$ . A (simple) $d$ -uniform hypergraph $G$ on $[N]$ is specified by an edge set $E\subseteq \binom{[N]}{d}$ . Let $\mathcal{G}_d(N,1/2)$ denote the Erdos-Renyi $d$ -uniform hypergraph distribution in which each $d$ -set $e\in\binom{[N]}{d}$ is included in $E$ independently with probability $1/2$ (Luo & Zhang (2020)).

For an integer $\kappa\in\{1,\dots,N\}$ , define the hypergraphic planted clique (HPC) distribution $\mathcal{G}_d(N,1/2,\kappa)$ by: draw $G\sim\mathcal{G}_d(N,1/2)$ ; sample a uniformly random subset $K\subseteq [N]$ with $|K|=\kappa$ ; then set every hyperedge $e\subseteq K$ with $|e|=d$ to be present (so the induced $d$ -uniform subhypergraph on $K$ is complete).

The $d\text{-HPC}$ detection problem is the average-case hypothesis test

H_0: G\sim \mathcal{G}_d(N,1/2) \quad\text{vs.}\quad H_1: G\sim \mathcal{G}_d(N,1/2,\kappa).

A (randomized) polynomial-time test is a family of algorithms $\{\phi_N\}$ running in time $\mathrm{poly}(N)$ and outputting $\phi_N(G)\in\{0,1\}$ . The test succeeds if its total error $\Pr_{H_0}[\phi_N(G)=1]+\Pr_{H_1}[\phi_N(G)=0]\to 0$ as $N\to\infty$ . For $d=2$ , this reduces to planted clique (PC) detection on graphs (Luo & Zhang (2020)). In this case, $\mathcal{G}_2(N,1/2,\kappa)$ is generated by first drawing an Erdos-Renyi graph from $\mathcal{G}_2(N,1/2)$ and then forcing all edges inside a uniformly random size- $\kappa$ vertex subset to be present.

The phrase "computationally equivalent" here means average-case randomized polynomial-time reductions in both directions (PC $\leftrightarrow$ $d\text{-HPC}$ ) that preserve null and planted distributions up to vanishing total-variation error and keep planted sizes asymptotically comparable (for example, $\kappa'=\kappa\cdot N^{o(1)}$ ) (Brennan et al. (2018)).

Unsolved Problem

In the regime $\kappa=o(\sqrt{N})$ (e.g. $\kappa=O(N^{1/2-\tau})$ for any fixed $\tau>0$ ), prove or refute such an average-case reduction from PC detection to $d\text{-HPC}$ detection.

Concretely, determine whether there exist $N'\le\mathrm{poly}(N)$ , $\kappa'=\kappa\cdot N^{o(1)}$ , and a randomized map $R$ computable in $\mathrm{poly}(N)$ time such that (1) if $G\sim\mathcal{G}_2(N,1/2)$ , then $R(G)$ is distributed as $\mathcal{G}_d(N',1/2)$ up to total variation error $o(1)$ , and (2) if $G\sim\mathcal{G}_2(N,1/2,\kappa)$ , then $R(G)$ is distributed as $\mathcal{G}_d(N',1/2,\kappa')$ up to total variation error $o(1)$ .

Equivalently, would any polynomial-time test for $d\text{-HPC}$ at planted size $\kappa'$ imply, via $R$ , a polynomial-time test for PC at planted size $\kappa$ in the corresponding regime?

§ Discussion

Loading discussion…

§ Significance & Implications

HPC detection is a common average-case starting point for reductions to tensor-structured inference tasks because a $d$ -uniform hypergraph can be represented by an order- $d$ adjacency tensor. Establishing a precise average-case reduction from PC to $d$ -HPC (or proving such a reduction cannot exist with comparable $\kappa$ ) would clarify whether hardness assumptions stated for $d$ -HPC in the regime $\kappa=o(\sqrt{N})$ are genuinely stronger/different than the standard planted clique conjecture, which directly affects the interpretability of hardness evidence for tensor problems built on $d$ -HPC as a base distribution.

§ Known Partial Results

Luo et al. (2020): Luo and Zhang (COLT 2020) formulate the $d$ -HPC detection problem and motivate it as an average-case hardness source for tensor problems.
Luo et al. (2020): Luo and Zhang (COLT 2020) ask for further evidence of average-case computational hardness of $d$ -HPC detection and, in particular, for evidence toward (or against) computational equivalence between $d$ -HPC detection and $d=2$ planted clique detection.
Luo et al. (2020): As summarized in Luo and Zhang (COLT 2020), spectral methods based on unfolding/matricizing the order- $d$ adjacency tensor provide polynomial-time detection in a high-signal regime (with threshold behavior on the order of $\kappa$ around $\sqrt{N}$ for fixed $d$ ), and are not expected to succeed deep in the regime $\kappa=O(N^{1/2-\tau})$ .
Luo et al. (2020): Luo and Zhang (COLT 2020) cite evidence for hardness of $d$ -HPC detection in restricted algorithmic frameworks (e.g. certain Markov chain/Metropolis-type approaches and the low-degree polynomial framework) in the regime $\kappa=O(N^{1/2-\tau})$ .
Luo et al. (2020): There is a simple polynomial-time mapping from a $d$ -uniform hypergraph to a graph by fixing a $(d-2)$ -subset $S\subseteq[N]$ and connecting $i,j$ when $S\cup\{i,j\}$ is a hyperedge; under $H_0$ this yields an Erdos-Renyi graph with edge probability $1/2$ , while under $H_1$ it yields a planted-clique graph conditional on the event $S\subseteq K$ (and is otherwise null-like). The open challenge is a reduction in the opposite direction (PC to $d$ -HPC) that preserves $\kappa$ up to asymptotic comparability without relying on such conditioning.