# A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials

arXiv: https://arxiv.org/abs/2504.03097 · HTML: https://mlsanity.com/paper/2504.03097/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 69 references that are in the map.
- First posted on arXiv 4 Apr 2025.

## Builds on (most cited first, 30 of 34)

- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Unsupervised Alignment of Embeddings with Wasserstein Procrustes](https://mlsanity.com/paper/1805.11222/) (2018)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Continuous LWE](https://mlsanity.com/paper/2005.09595/) (2020)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [Linear regression without correspondence](https://mlsanity.com/paper/1705.07048/) (2017)
- [Optimal Low-Degree Hardness of Maximum Independent Set](https://mlsanity.com/paper/2010.06563/) (2020)
- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data](https://mlsanity.com/paper/1907.07148/) (2019)
- [Counterexamples to the Low-Degree Conjecture](https://mlsanity.com/paper/2004.08454/) (2020)
- [Strong recovery of geometric planted matchings](https://mlsanity.com/paper/2107.05567/) (2021)
- [Linear Regression with Shuffled Labels](https://mlsanity.com/paper/1705.01342/) (2017)
- [Low-Degree Hardness of Detection for Correlated ErdHos-R'enyi Graphs](https://mlsanity.com/paper/2311.15931/) (2023)
- [Exact Recovery with Symmetries for Procrustes Matching](https://mlsanity.com/paper/1606.01548/) (2016)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing from Multiple Measurement Vectors](https://mlsanity.com/paper/1909.02496/) (2019)
- [The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime](https://mlsanity.com/paper/2402.15095/) (2024)
- [A computational transition for detecting correlated stochastic block models by low-degree polynomials](https://mlsanity.com/paper/2409.00966/) (2024)

## Abstract (arXiv)

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 model Y=tfrac1√1+σ2(Pi_* X Q_* + σ Z), where X is an n*d standard Gaussian design matrix, Z is an n*m Gaussian noise matrix, Pi_* is an unknown n*n permutation matrix, and Q_* is an unknown d*m on the Grassmanian manifold satisfying Q_*top Q_* = mathbb Im. Consider the hypothesis testing problem of distinguishing this model from the case where X and Y are independent Gaussian random matrices of sizes n*d and n*m, respectively. Our results reveal a phase transition phenomenon in the performance of low-degree polynomial algorithms for this task. (1) When m=o(d), we show that all degree-D polynomials fail to distinguish these two models even when σ=0, provided with D4=obig( tfracdm big). (2) When m=d and σ=ω(1), we show that all degree-D polynomials fail to distinguish these two models provided with D=o(σ). (3) When m=d and σ=o(1), we show that there exists a constant-degree 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 dimensions m and d, the noise level σ, and the computational complexity of the testing task.