Computational lower bounds for multi-frequency group synchronization

We consider a group synchronization problem with multiple frequencies which involves observing pairwise relative measurements of group elements on multiple frequency channels, corrupted by Gaussian noise. We study the computational phase transition in the problem of detecting whether a structured signal is present in such observations by analyzing low-degree polynomial algorithms. We show that, assuming the low-degree conjecture, in synchronization models over arbitrary finite groups as well as over the circle group SO (2), a simple spectral algorithm is optimal among algorithms of runtime exp ( Ω ˜ ( n 1 / 3 ) ) for detection from an observation including a constant number of frequencies. Combined with an upper bound for the statistical threshold shown in Perry et al. 1, our results indicate the presence of a statistical-to-computational gap in such models with a sufficiently large number of frequencies.