Computational barriers to estimation from low-degree polynomials (Q2149001): Difference between revisions

@@ Property / describes a project that uses @@
+LAS
@@ Property / describes a project that uses: LAS / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+On basing one-way functions on NP-hardness
@@ Property / cites work: On basing one-way functions on NP-hardness / rank @@
+Normal rank
@@ Property / cites work @@
+Detection of an anomalous cluster in a network
@@ Property / cites work: Detection of an anomalous cluster in a network / rank @@
+Normal rank
@@ Property / cites work @@
+Community detection in dense random networks
@@ Property / cites work: Community detection in dense random networks / rank @@
+Normal rank
@@ Property / cites work @@
+Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
+Normal rank
@@ Property / cites work @@
+Eigenvalues of large sample covariance matrices of spiked population models
+Normal rank
@@ Property / cites work @@
+Q5875785
@@ Property / cites work: Q5875785 / rank @@
+Normal rank
@@ Property / cites work @@
+The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
+Normal rank
@@ Property / cites work @@
+A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
+Normal rank
@@ Property / cites work @@
+The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
+Normal rank
@@ Property / cites work @@
+Algorithmic thresholds for tensor PCA
@@ Property / cites work: Algorithmic thresholds for tensor PCA / rank @@
+Normal rank
@@ Property / cites work @@
+The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
+Normal rank
@@ Property / cites work @@
+Detecting high log-densities
@@ Property / cites work: Detecting high log-densities / rank @@
+Normal rank
@@ Property / cites work @@
+How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA
+Normal rank
@@ Property / cites work @@
+On Worst‐Case to Average‐Case Reductions for NP Problems
+Normal rank
@@ Property / cites work @@
+An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
+Normal rank
@@ Property / cites work @@
+Detection of a sparse submatrix of a high-dimensional noisy matrix
+Normal rank
@@ Property / cites work @@
+Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
+Normal rank
@@ Property / cites work @@
+Computational and statistical boundaries for submatrix localization in a large noisy matrix
+Normal rank
@@ Property / cites work @@
+Statistical and computational limits for sparse matrix detection
+Normal rank
@@ Property / cites work @@
+The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
+Normal rank
@@ Property / cites work @@
+Suboptimality of local algorithms for a class of max-cut problems
+Normal rank
@@ Property / cites work @@
+Incoherence-Optimal Matrix Completion
@@ Property / cites work: Incoherence-Optimal Matrix Completion / rank @@
+Normal rank
@@ Property / cites work @@
+Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
+Normal rank
@@ Property / cites work @@
+Q5009502
@@ Property / cites work: Q5009502 / rank @@
+Normal rank
@@ Property / cites work @@
+Walksat Stalls Well Below Satisfiability
@@ Property / cites work: Walksat Stalls Well Below Satisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+Asymptotic mutual information for the balanced binary stochastic block model
+Normal rank
@@ Property / cites work @@
+Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
+Normal rank
@@ Property / cites work @@
+Higher criticism for detecting sparse heterogeneous mixtures.
+Normal rank
@@ Property / cites work @@
+Q4999009
@@ Property / cites work: Q4999009 / rank @@
+Normal rank
@@ Property / cites work @@
+Random-Self-Reducibility of Complete Sets
@@ Property / cites work: Random-Self-Reducibility of Complete Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
+Normal rank
@@ Property / cites work @@
+The largest eigenvalue of rank one deformation of large Wigner matrices
+Normal rank
@@ Property / cites work @@
+The overlap gap property and approximate message passing algorithms for \(p\)-spin models
+Normal rank
@@ Property / cites work @@
+The overlap gap property in principal submatrix recovery
+Normal rank
@@ Property / cites work @@
+Limits of local algorithms over sparse random graphs
+Normal rank
@@ Property / cites work @@
+Sparse CCA: adaptive estimation and computational barriers
+Normal rank
@@ Property / cites work @@
+Submatrix localization via message passing
@@ Property / cites work: Submatrix localization via message passing / rank @@
+Normal rank
@@ Property / cites work @@
+Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
+Normal rank
@@ Property / cites work @@
+State evolution for general approximate message passing algorithms, with applications to spatial coupling
+Normal rank
@@ Property / cites work @@
+On Consistency and Sparsity for Principal Components Analysis in High Dimensions
+Normal rank
@@ Property / cites work @@
+Efficient noise-tolerant learning from statistical queries
+Normal rank
@@ Property / cites work @@
+Sum of squares lower bounds for refuting any CSP
@@ Property / cites work: Sum of squares lower bounds for refuting any CSP / rank @@
+Normal rank
@@ Property / cites work @@
+Computational barriers in minimax submatrix detection
+Normal rank
@@ Property / cites work @@
+Lifting sum-of-squares lower bounds: degree-2 to degree-4
+Normal rank
@@ Property / cites work @@
+Estimation of low-rank matrices via approximate message passing
+Normal rank
@@ Property / cites work @@
+On the degree of Boolean functions as real polynomials
+Normal rank
@@ Property / cites work @@
+Q2930842
@@ Property / cites work: Q2930842 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimality and sub-optimality of PCA. I: Spiked random matrix models
+Normal rank
@@ Property / cites work @@
+HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
+Normal rank
@@ Property / cites work @@
+Local algorithms for independent sets are half-optimal
+Normal rank
@@ Property / cites work @@
+Finding large average submatrices in high dimensional data
+Normal rank
@@ Property / cites work @@
+Community detection in sparse random networks
@@ Property / cites work: Community detection in sparse random networks / rank @@
+Normal rank
@@ Property / cites work @@
+Statistical and computational trade-offs in estimation of sparse principal components
+Normal rank
@@ Property / cites work @@
+Optimal low-degree hardness of maximum independent set
+Normal rank
@@ Property / cites work @@
+Tensor SVD: Statistical and Computational Limits
@@ Property / cites work: Tensor SVD: Statistical and Computational Limits / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:2149001