Computational barriers to estimation from low-degree polynomials

Publication date: 24 June 2022

Published in: The Annals of Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2008.02269

zbMATH Keywords

computational complexity low-degree polynomials planted dense subgraph planted submatrix

Mathematics Subject Classification ID

Bayesian inference (62F15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics

Uses Software

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Statistical and computational trade-offs in estimation of sparse principal components
An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
Algorithmic thresholds for tensor PCA
Community detection in sparse random networks
Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
Finding large average submatrices in high dimensional data
The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
On the degree of Boolean functions as real polynomials
Sparse CCA: adaptive estimation and computational barriers
Optimality and sub-optimality of PCA. I: Spiked random matrix models
Higher criticism for detecting sparse heterogeneous mixtures.
Local algorithms for independent sets are half-optimal
The overlap gap property in principal submatrix recovery
Optimal low-degree hardness of maximum independent set
Statistical and computational limits for sparse matrix detection
The overlap gap property and approximate message passing algorithms for \(p\)-spin models
Computational barriers in minimax submatrix detection
Computational and statistical boundaries for submatrix localization in a large noisy matrix
Suboptimality of local algorithms for a class of max-cut problems
Detection of an anomalous cluster in a network
Detection of a sparse submatrix of a high-dimensional noisy matrix
The largest eigenvalue of rank one deformation of large Wigner matrices
Eigenvalues of large sample covariance matrices of spiked population models
Community detection in dense random networks
Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
Estimation of low-rank matrices via approximate message passing
Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
Detecting high log-densities
On basing one-way functions on NP-hardness
Incoherence-Optimal Matrix Completion
Random-Self-Reducibility of Complete Sets
Efficient noise-tolerant learning from statistical queries
Submatrix localization via message passing
Tensor SVD: Statistical and Computational Limits
Asymptotic mutual information for the balanced binary stochastic block model
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
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
Lifting sum-of-squares lower bounds: degree-2 to degree-4
State evolution for general approximate message passing algorithms, with applications to spatial coupling
The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
On Consistency and Sparsity for Principal Components Analysis in High Dimensions
Walksat Stalls Well Below Satisfiability
The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
On Worst‐Case to Average‐Case Reductions for NP Problems
Limits of local algorithms over sparse random graphs

This page was built for publication: Computational barriers to estimation from low-degree polynomials