Computational lower bounds for multi-frequency group synchronization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909217635434496 |
|---|---|
| author | Kireeva, Anastasia Bandeira, Afonso S. Kunisky, Dmitriy |
| author_facet | Kireeva, Anastasia Bandeira, Afonso S. Kunisky, Dmitriy |
| contents | 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(\tildeΩ(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., our results indicate the presence of a statistical-to-computational gap in such models with a sufficiently large number of frequencies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_03424 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computational lower bounds for multi-frequency group synchronization Kireeva, Anastasia Bandeira, Afonso S. Kunisky, Dmitriy Statistics Theory Computational Complexity Probability 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(\tildeΩ(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., our results indicate the presence of a statistical-to-computational gap in such models with a sufficiently large number of frequencies. |
| title | Computational lower bounds for multi-frequency group synchronization |
| topic | Statistics Theory Computational Complexity Probability |
| url | https://arxiv.org/abs/2406.03424 |