Average-case complexity of tensor decomposition for low-degree polynomials

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Optimal detection of sparse principal components in high dimension
Refined methods for the identifiability of tensors
Algorithmic thresholds for tensor PCA
The overlap gap property in principal submatrix recovery
Community detection on mixture multilayer networks via regularized tensor decomposition
Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
Optimal low-degree hardness of maximum independent set
Tensor clustering with planted structures: statistical optimality and computational limits
Sparse high-dimensional linear regression. Estimating squared error and a phase transition
On the optimization landscape of tensor decompositions
Computational barriers to estimation from low-degree polynomials
A spectral algorithm for latent Dirichlet allocation
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Learning Mixtures of Gaussians in High Dimensions
Learning mixtures of spherical gaussians
A Decomposition for Three-Way Arrays
Algorithmic Aspects of Machine Learning
Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
Large Cliques Elude the Metropolis Process
Fourth-Order Cumulant-Based Blind Identification of Underdetermined Mixtures
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
Bispectrum Inversion With Application to Multireference Alignment
Tensor Decomposition for Signal Processing and Machine Learning
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
Sum of squares lower bounds for refuting any CSP
The Sample Complexity of Multireference Alignment
The Average-Case Time Complexity of Certifying the Restricted Isometry Property
Disordered systems insights on computational hardness
How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA
HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
Spectral methods from tensor networks
Fourier PCA and robust tensor decomposition
Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Most Tensor Problems Are NP-Hard
Learning nonsingular phylogenies and hidden Markov models
Limits of local algorithms over sparse random graphs
Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
Free Energy Wells and Overlap Gap Property in Sparse PCA
A stress-free sum-of-squares lower bound for coloring
Estimation under group actions: recovering orbits from invariants

This page was built for publication: Average-case complexity of tensor decomposition for low-degree polynomials