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

Cites Work

Optimal detection of sparse principal components in high dimension
A tensor approach to learning mixed membership community models
Most tensor problems are NP-hard
Large Cliques Elude the Metropolis Process
Fourth-Order Cumulant-Based Blind Identification of Underdetermined Mixtures
Limits of local algorithms over sparse random graphs
A Decomposition for Three-Way Arrays
Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
Refined methods for the identifiability of tensors
Sparse high-dimensional linear regression. Estimating squared error and a phase transition
Tensor Decomposition for Signal Processing and Machine Learning
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Algorithmic thresholds for tensor PCA
Learning mixtures of Gaussians in high dimensions
Algorithmic aspects of machine learning
A spectral algorithm for latent Dirichlet allocation
Title not available (Why is that?)
Estimation under group actions: recovering orbits from invariants
A stress-free sum-of-squares lower bound for coloring
Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
Sum of squares lower bounds for refuting any CSP
Analyzing tensor power method dynamics in overcomplete regime
On the optimization landscape of tensor decompositions
Dictionary learning and tensor decomposition via the sum-of-squares method
Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms
Bispectrum Inversion With Application to Multireference Alignment
The overlap gap property in principal submatrix recovery
Statistical algorithms and a lower bound for detecting planted cliques
Community detection on mixture multilayer networks via regularized tensor decomposition
Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
Optimal low-degree hardness of maximum independent set
Tensor clustering with planted structures: statistical optimality and computational limits
The Average-Case Time Complexity of Certifying the Restricted Isometry Property
The sample complexity of multireference alignment
Spectral methods from tensor networks
Fourier PCA and robust tensor decomposition
Computational barriers to estimation from low-degree polynomials
How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA
On the integrality gap of degree-4 sum of squares for planted clique
Disordered systems insights on computational hardness
Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
Free Energy Wells and Overlap Gap Property in Sparse PCA

Cited In (1)

Computational lower bounds for graphon estimation via low-degree polynomials

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

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