Computational barriers to estimation from low-degree polynomials (Q2149001)

scientific article; zbMATH DE number 7547952

Language	Label	Description	Also known as
English	Computational barriers to estimation from low-degree polynomials	scientific article; zbMATH DE number 7547952

Statements

instance of

scholarly article

0 references

title

Computational barriers to estimation from low-degree polynomials (English)

0 references

0 references

0 references

The Annals of Statistics

0 references

publication date

24 June 2022

0 references

full work available at URL

https://arxiv.org/abs/2008.02269

0 references

zbMATH Keywords

computational complexity

0 references

low-degree polynomials

0 references

planted dense subgraph

0 references

planted submatrix

0 references

describes a project that uses

0 references

0 references

On basing one-way functions on NP-hardness

0 references

Detection of an anomalous cluster in a network

0 references

Community detection in dense random networks

0 references

Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices

0 references

Eigenvalues of large sample covariance matrices of spiked population models

0 references

Q5875785

0 references

The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime

0 references

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

0 references

The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing

0 references

Algorithmic thresholds for tensor PCA

0 references

The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

0 references

Detecting high log-densities

0 references

How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA

0 references

On Worst‐Case to Average‐Case Reductions for NP Problems

0 references

An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model

0 references

Detection of a sparse submatrix of a high-dimensional noisy matrix

0 references

Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix

0 references

Computational and statistical boundaries for submatrix localization in a large noisy matrix

0 references

Statistical and computational limits for sparse matrix detection

0 references

The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations

0 references

Suboptimality of local algorithms for a class of max-cut problems

0 references

Incoherence-Optimal Matrix Completion

0 references

Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices

0 references

Q5009502

0 references

Walksat Stalls Well Below Satisfiability

0 references

Asymptotic mutual information for the balanced binary stochastic block model

0 references

Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time

0 references

Higher criticism for detecting sparse heterogeneous mixtures.

0 references

Q4999009

0 references

Random-Self-Reducibility of Complete Sets

0 references

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques

0 references

The largest eigenvalue of rank one deformation of large Wigner matrices

0 references

The overlap gap property and approximate message passing algorithms for \(p\)-spin models

0 references

The overlap gap property in principal submatrix recovery

0 references

Limits of local algorithms over sparse random graphs

0 references

Sparse CCA: adaptive estimation and computational barriers

0 references

Submatrix localization via message passing

0 references

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

0 references

State evolution for general approximate message passing algorithms, with applications to spatial coupling

0 references

On Consistency and Sparsity for Principal Components Analysis in High Dimensions

0 references

Efficient noise-tolerant learning from statistical queries

0 references

Sum of squares lower bounds for refuting any CSP

0 references

Computational barriers in minimax submatrix detection

0 references

Lifting sum-of-squares lower bounds: degree-2 to degree-4

0 references

Estimation of low-rank matrices via approximate message passing

0 references

On the degree of Boolean functions as real polynomials

0 references

Q2930842

0 references

Optimality and sub-optimality of PCA. I: Spiked random matrix models

0 references

HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS

0 references

Local algorithms for independent sets are half-optimal

0 references

Finding large average submatrices in high dimensional data

0 references

Community detection in sparse random networks

0 references

Statistical and computational trade-offs in estimation of sparse principal components

0 references

Optimal low-degree hardness of maximum independent set

0 references

Tensor SVD: Statistical and Computational Limits

0 references

Identifiers

DOI

10.1214/22-AOS2179

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2149001