From low-degree hardness to unconditional polynomial-time hardness

For each $n$, let $[n]=\{1,\dots,n\}$ and $U_n=\{\{i,j\}:1\le i<j\le n\}$. Fix constants $k\ge 2$, $\lambda>0$, $\epsilon\in(0,1)$, and subsampling rate $s\in(0,1)$, with $k,\lambda=O(1)$ as $n\to\infty$.

This setup follows Chen et al. (2025).

The formal correlated-SBM model and detection setup below follow the source paper. First sample latent labels $\sigma^\*\in[k]^n$ uniformly (equivalently, i.i.d. uniform on $[k]$). Conditional on $\sigma^\*$, sample independent edges $(G_{ij})_{\{i,j\}\in U_n}$ with

Then sample independent Bernoulli$(s)$ variables $(J_{ij})_{\{i,j\}\in U_n}$ and $(K_{ij})_{\{i,j\}\in U_n}$, and an independent uniform permutation $\pi^\*\in S_n$. The observed pair $(A,B)$ is

Let $P_n$ be the law of $(A,B)$ (after marginalizing $\sigma^\*,\pi^\*,G,J,K$). Let $Q_n$ be the null law where $A$ and $B$ are independent Erd\H{o}s-R'enyi graphs $G(n,\lambda s/n)$.

The detection problem is to construct tests $\varphi_n:\{0,1\}^{U_n}\times\{0,1\}^{U_n}\to\{0,1\}$; success with vanishing error means

A randomized polynomial-time test means runtime $n^{O(1)}$ (including internal randomness).

A partial matching estimator is a randomized polynomial-time map $\widehat\pi_n(A,B)\in S_n$. One concrete notion of nontrivial partial recovery is: there exists $\eta>0$ such that

Let $\alpha\approx 0.338$ denote the Otter constant in this paper's notation, i.e., the inverse of the classical rooted-tree growth constant $\rho\approx 2.955765\ldots$ (so $\alpha=1/\rho$), equivalently $t_m=\Theta(\alpha^{-m}m^{-3/2})$ for unlabeled rooted trees.

The source establishes a sharp transition for low-degree methods but leaves unconditional polynomial-time hardness open.