Computational lower bounds for multi-frequency group synchronization

DOI10.1016/J.ACHA.2026.101880MaRDI QIDQ7268668zbMATH OpenFDO

Authors Anastasia Kireeva, Afonso S. Bandeira, Dmitriy Kunisky

Publication date 18 June 2026

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ACHA.2026.101880

zbMATH Keywords

computational complexityprobabilitygroup synchronizationstatistics theory

Mathematics Subject Classification ID

Statistics (62-XX) Information and communication theory, circuits (94-XX)

Cites work

• scientific article; zbMATH DE number 3169867 (Why is no real title available?)
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Algorithmic thresholds for tensor PCA
• Angular synchronization by eigenvectors and semidefinite programming
• Asymptotic mutual information for the balanced binary stochastic block model
• Computational barriers to estimation from low-degree polynomials
• Efficient Bayesian estimation from few samples: community detection and related problems
• Efficient noise-tolerant learning from statistical queries
• Exact Recovery in the Stochastic Block Model
• Message-passing algorithms for synchronization problems over compact groups
• Multireference alignment using semidefinite programming
• Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• Non-unique games over compact groups and orientation estimation in cryo-EM
• Nonlinear Dimensionality Reduction
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• On the concentration of Gaussian Cayley matrices
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Phase transitions in semidefinite relaxations
• Sensor network localization on the group of three-dimensional displacements
• Sharp and simple bounds for the raw moments of the binomial and Poisson distributions
• Statistical algorithms and a lower bound for detecting planted cliques
• The Elements of Statistical Learning
• The Kikuchi hierarchy and tensor PCA
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The power of sum-of-squares for detecting hidden structures
• Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

This page was built for publication: Computational lower bounds for multi-frequency group synchronization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7268668)