Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
From MaRDI portal
Publication:2103494
Cites work
- scientific article; zbMATH DE number 3169867 (Why is no real title available?)
- scientific article; zbMATH DE number 1273988 (Why is no real title available?)
- scientific article; zbMATH DE number 2171466 (Why is no real title available?)
- scientific article; zbMATH DE number 1380608 (Why is no real title available?)
- scientific article; zbMATH DE number 3037624 (Why is no real title available?)
- scientific article; zbMATH DE number 7650426 (Why is no real title available?)
- A nearly tight sum-of-squares lower bound for the planted clique problem
- A proof of the block model threshold conjecture
- Algorithmic thresholds for tensor PCA
- Almost all cubic graphs are Hamiltonian
- Almost all regular graphs are hamiltonian
- Analysis of Boolean Functions
- Asymptotic mutual information for the balanced binary stochastic block model
- Color-coding
- Community detection thresholds and the weak Ramanujan property
- Do semidefinite relaxations solve sparse PCA up to the information limit?
- Efficient noise-tolerant learning from statistical queries
- Expected complexity of graph partitioning problems
- Factoring polynomials with rational coefficients
- Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Fundamental limits of detection in the spiked Wigner model
- Fundamental limits of symmetric low-rank matrix estimation
- Gaussian Hilbert Spaces
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Global optimization with polynomials and the problem of moments
- HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
- Heuristics for semirandom graph problems
- IX. On the problem of the most efficient tests of statistical hypotheses
- Information, Physics, and Computation
- Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
- Large Cliques Elude the Metropolis Process
- Limits of local algorithms over sparse random graphs
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Noise-tolerant learning, the parity problem, and the statistical query model
- Notes on computational-to-statistical gaps: predictions using statistical physics
- On Counting Independent Sets in Sparse Graphs
- On consistency and sparsity for principal components analysis in high dimensions
- On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
- On the complexity of random satisfiability problems with planted solutions
- Optimal detection of sparse principal components in high dimension
- Optimality and sub-optimality of PCA. I: Spiked random matrix models
- Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
- Random matrices and complexity of spin glasses
- Reconstruction and estimation in the planted partition model
- Robust estimators in high-dimensions without the computational intractability
- Sparse PCA via covariance thresholding
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition
- Spectral redemption in clustering sparse networks
- Statistical algorithms and a lower bound for detecting planted cliques
- Statistical and computational trade-offs in estimation of sparse principal components
- Statistical limits of spiked tensor models
- Statistical thresholds for tensor PCA
- Strongly refuting random CSPs below the spectral threshold
- Suboptimality of local algorithms for a class of max-cut problems
- Sum of squares lower bounds for refuting any CSP
- Sum-of-squares Lower Bounds for Planted Clique
- Sum-of-squares certificates for maxima of random tensors on the sphere
- Sum-of-squares proofs and the quest toward optimal algorithms
- Testing Statistical Hypotheses
- The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
- The largest eigenvalue of rank one deformation of large Wigner matrices
- Unconditional lower bounds for learning intersections of halfspaces
Cited in
(12)- Algorithmic obstructions in the random number partitioning problem
- Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
- Public-key encryption, local pseudorandom generators, and the low-degree method
- Optimal estimation and computational limit of low-rank Gaussian mixtures
- Free Energy Wells and Overlap Gap Property in Sparse PCA
- Matrix denoising: Bayes-optimal estimators via low-degree polynomials
- Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
- Computational lower bounds for graphon estimation via low-degree polynomials
- Computational and statistical thresholds in multi-layer stochastic block models
- Average-case complexity of tensor decomposition for low-degree polynomials
- Algorithms approaching the threshold for semi-random planted clique
- Sum-of-squares lower bounds for densest \(k\)-subgraph
This page was built for publication: Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2103494)
