{"id":"arxiv/2601.20522","url":"https://arxiv.org/abs/2601.20522","tags":["math.ST","cs.DS","math.PR"],"score":0,"title":"Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization","domain":"math.ST","source":"arxiv","authors":["Zhangsong Li"],"reviews":0,"subject":"math.ST","summary":"We study the computational phase transition in a multi-frequency group synchronization problem, where pairwise relative measurements of group elements are observed across multiple frequency channels and corrupted by Gaussian noise. Using the framework of \\emph{low-degree polynomial algorithms}, we analyze the task of estimating the structured signal in such observations. We show that, assuming the low-degree heuristic, in synchronization models over the circle group $\\mathsf{SO}(2)$, a simple spectral method is computationally optimal among all polynomial-time estimators when the number of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-28","reactions":{}}