Sub-exponential detection in the hard regime of multi-frequency synchronization
In multi-frequency synchronization over $SO(2) \cong U(1)$, a signal $x \in U(1)^n$ is observed through $L$ frequencies, $$Y_k = \frac{\lambda}{n}\, x^{(k)}\bigl(x^{(k)}\bigr)^* + \frac{1}{\sqrt n}\, W^{(k)}, \qquad k = 1, \dots, L,$$ where $x^{(k)}$ is the entrywise $k$-th power of $x$ and $W^{(1)}, \dots, W^{(L)}$ are independent GUE noise matrices; over a finite group the frequencies are its irreducible representations (Perry, Wein, Bandeira and Moitra). The signal is uniform over the group. For the cyclic group $\mathbb{Z}/L\mathbb{Z}$, Perry, Wein, Bandeira and Moitra showed that the statistical threshold is $\lambda_{\mathrm{stat}} = \Theta(\sqrt{\log L / L})$: for a finite group of order $L$, their exponential-time test detects the signal once $\lambda > \sqrt{4 \log L / (L - 1)}$, which is below the spectral threshold $1$ once $L \ge 11$. Assuming the low-degree conjecture, no polynomial-time algorithm does so for constant $L$ (Kireeva, Bandeira and Kunisky).
Problem. Fix $L$, independent of $n$, and let $\lambda \in (\lambda_{\mathrm{stat}}, 1)$. Is there an algorithm running in time $\exp(n^\delta)$ for some $\delta < 1$ that detects the signal reliably as $n \to \infty$?
Source: Kireeva, Open Problem 8 of Randomstrasse101, in “Detection in Multi-Frequency synchronization” (2024); Entry 4 of arXiv:2504.20539.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- ST — Statistics Theory
- Secondary
- PR
- Keywords
- group synchronization, Randomstrasse101, spiked random matrices, statistical-to-computational gaps
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2024,
author = {Bandeira, Afonso S. and Kireeva, Anastasia and Maillard, Antoine and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2024},
year = {2025},
eprint = {2504.20539},
archivePrefix = {arXiv}
}
@misc{kireeva2024multifrequency,
author = {Kireeva, Anastasia and Bandeira, Afonso S. and Kunisky, Dmitriy},
title = {Computational lower bounds for multi-frequency group synchronization},
year = {2024},
eprint = {2406.03424},
archivePrefix = {arXiv}
}
@misc{perry2016pca,
author = {Perry, Amelia and Wein, Alexander S. and Bandeira, Afonso S. and Moitra, Ankur},
title = {Optimality and sub-optimality of {PCA} for spiked random matrices and synchronization},
year = {2016},
eprint = {1609.05573},
archivePrefix = {arXiv}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00030, "Sub-exponential detection in the hard regime of multi-frequency synchronization", clopen.solutions.