Consider a pair of sparse correlated stochastic block models \(\mathcal S(n, \tfrac{\lambda}{n}; \epsilon; \mathcal s)\) subsampled from a common parent stochastic block model with two symmetric communities, average degree \(\lambda = O(1)\), divergence parameter \(\epsilon \in (0,1)\) and subsampling probability \(\mathcal s\). For all \(\epsilon \in (0,1)\), we construct a statistic based on the combination of two low-degree polynomials and show that there exists a sufficiently small constant \(\delta = \delta(\epsilon) \gt 0\) and a sufficiently large constant \(\Delta = \Delta(\epsilon, \delta)\) such that when \(\lambda \gt \Delta\) and \(\mathcal s \gt \sqrt{\alpha} - \delta\) where \(\alpha \approx 0.338\) is Otter’s constant, this statistic can distinguish this model and a pair of independent stochastic block models \(\mathcal S(n, \tfrac{\lambda s}{n}, \epsilon)\) with probability \(1 - o(1)\). We also provide an efficient algorithm that approximates this statistic in polynomial time. Our result is the first detection or matching type algorithm that breaks the Otter’s threshold in sparse correlated random graphs. The crux of our statistic’s construction lies in a carefully curated family of multigraphs called decorated trees, which enables effective aggregation of the community signal and graph correlation from the counts of the same decorated tree while suppressing the undesirable correlations among counts of different decorated trees. We believe such construction may be of independent interest.

In this paper, we study the problem of multivariate shuffled linear regression, where the correspondence between predictors and responses in a linear model is obfuscated by a latent permutation. Specifically, we investigate the modelY= (Π*XQ*+σZ)/√1+σ2, whereXis ann * dstandard Gaussian design matrix, Z is an n*m Gaussian noise matrix, Π*is an unknownn*npermutation matrix, andQ*is an unknownd * mon the Grassmanian manifold satisfyingQ*TQ*= Im. Consider the hypothesis testing problem of distinguishing this model from the case whereXandYare independent Gaussian random matrices of sizesn * dandn * m, respectively. Our results reveal a phase transition phenomenon in the performance oflow-degree polynomial algorithmsfor this task. (1) Whenm = o(d), we show that all degree-Dpolynomials fail to distinguish these two models even when σ = 0, provided withD4=o(d/m). (2) Whenm = dand σ = ω(1), we show that all degree-Dpolynomials fail to distinguish these two models provided withD=o(σ). (3) Whenm = dand σ =o(1), we show that there exists a constantdegree polynomial that strongly distinguish these two models. These results establish a smooth transition in the effectiveness of low-degree polynomial algorithms for this problem, highlighting the interplay between the dimensionsmandd, the noise level σ, and the computational complexity of the testing task.

In this paper, we focus on the matching recovery problem between a pair of correlated Gaussian Wigner matrices with a latent vertex correspondence. We are particularly interested in a robust version of this problem such that our observation is a perturbed input (A + E,B + F) where (A,B) is a pair of correlated Gaussian Wigner matrices andE, Fare adversarially chosen matrices supported on an unknown ϵn∗ ϵnprincipal minor of A,B, respectively. We propose an approximate message passing (AMP) type iterative algorithm that succeeds in polynomial time as long as the correlation ρ between (A,B) is a non-vanishing constant and ϵ = o( 1/(logn)20). A key distinction from standard AMP is the introduction of a time-dependent matrix multiplication step within the iteration, which simultaneously enlarges the feature dimension and cancels the correlation during the iteration. The main methodological inputs for our result are the iterative random graph matching algorithm proposed in [25], [26] and the spectral preprocessing procedure proposed in [48]. To the best of our knowledge, our algorithm is the first efficient random graph matching type algorithm that is robust under any adversarial perturbations ofn1−o(1)size.

In this paper, assuming the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correlated Erdős-Rényi graphs $\mathcal G(n,q;ρ)$ when the edge-density $q=n^{-1+o(1)}$ and the correlation $ρ<\sqrtα$ lies below the Otter's threshold, this resolves a remaining problem in \cite{DDL23+}; (2) the detection problem between a pair of correlated sparse stochastic block models $\mathcal S(n,\tfracλ{n};k,ε;s)$ and a pair of independent stochastic block models $\mathcal S(n,\tfrac{λs}{n};k,ε)$ when $ε^2 λs<1$ lies below the Kesten-Stigum (KS) threshold and $s<\sqrtα$ lies below the Otter's threshold, this resolves a remaining problem in \cite{CDGL24+}. One of the main ingredient in our proof is to derive certain forms of \emph{algorithmic contiguity} between two probability measures based on bounds on their low-degree advantage. To be more precise, consider the high-dimensional hypothesis testing problem between two probability measures $\mathbb{P}$ and $\mathbb{Q}$ based on the sample $\mathsf Y$. We show that if the low-degree advantage $\mathsf{Adv}_{\leq D} \big( \frac{\mathrm{d}\mathbb{P}}{\mathrm{d}\mathbb{Q}} \big)=O(1)$, then (assuming the low-degree conjecture) there is no efficient algorithm $\mathcal A$ such that $\mathbb{Q}(\mathcal A(\mathsf Y)=0)=1-o(1)$ and $\mathbb{P}(\mathcal A(\mathsf Y)=1)=Ω(1)$. This framework provides a useful tool for performing reductions between different inference tasks, without requiring a strengthened version of the low-degree conjecture as in \cite{MW23+, DHSS25+}.

In this paper, we focus on the matching recovery problem between a pair of correlated Gaussian Wigner matrices with a latent vertex correspondence. Although Polynomial-time algorithms for graph matching have been studied in the line of work (Barak et al. (2019); Ding et al. (2021); Fan et al. (2023a,b); Ganassali and Massoulié (2020); Ganassali et al. (2024a); Mao et al. (2021, 2023a); Ganassali et al. (2024b); Mao et al. (2023b); Ding and Li (2025+, 2023)), many of the efficient algorithms used to achieve matching recovery are believed to be fragile in the sense that adversarially modifying a small fraction of edges could fool the algorithm into outputting a result which deviates strongly from the true underlying matching. Thus, we are particularly interested in a robust version of this problem such that our observation is a perturbed input $(A+E,B+F)$ where $(A,B)$ is a pair of correlated Gaussian Wigner matrices and $E,F$ are adversarially chosen matrices supported on an unknown $\epsilon n * \epsilon n$ principle minor of $A,B$, respectively. We propose a vector approximate message passing (vector AMP) algorithm that succeeds in polynomial time as long as the correlation $\rho$ between $(A,B)$ is a non-vanishing constant and $\epsilon = o\big( \frac{1}{(\log n)^{20}} \big)$. The main methodological inputs for our result are the iterative random graph matching algorithm proposed in Ding and Li (2025+, 2023) and the spectral cleaning procedure proposed in Ivkov and Schramm (2025). To the best of our knowledge, our algorithm is the first efficient random graph matching type algorithm that is robust under any adversarial perturbations of $n^{1-o(1)}$ size.