Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio

DOI10.1007/978-3-030-97127-4_1OpenAlexW2964738308MaRDI QIDQ2103494FDOQ2103494

Authors: Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira

Publication date: 13 December 2022

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

hypothesis testing low-degree likelihood ratio statistical-to-computational gaps

Factor analysis and principal components; correspondence analysis (62H25) Hypothesis testing in multivariate analysis (62H15)

Cites Work

Testing Statistical Hypotheses
A proof of the block model threshold conjecture
Spectral redemption in clustering sparse networks
Reconstruction and estimation in the planted partition model
On consistency and sparsity for principal components analysis in high dimensions
Community detection thresholds and the weak Ramanujan property
IX. On the problem of the most efficient tests of statistical hypotheses
Optimal detection of sparse principal components in high dimension
Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
Title not available (Why is that?)
Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
Global optimization with polynomials and the problem of moments
Title not available (Why is that?)
Title not available (Why is that?)
Factoring polynomials with rational coefficients
Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
Gaussian Hilbert Spaces
Color-coding
Sum-of-squares proofs and the quest toward optimal algorithms
Analysis of Boolean Functions
Title not available (Why is that?)
The largest eigenvalue of rank one deformation of large Wigner matrices
The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
Gibbs states and the set of solutions of random constraint satisfaction problems
On Counting Independent Sets in Sparse Graphs
Efficient noise-tolerant learning from statistical queries
Large Cliques Elude the Metropolis Process
Random matrices and complexity of spin glasses
Information, Physics, and Computation
Noise-tolerant learning, the parity problem, and the statistical query model
Title not available (Why is that?)
Almost all regular graphs are hamiltonian
Statistical and computational trade-offs in estimation of sparse principal components
Almost all cubic graphs are Hamiltonian
Unconditional lower bounds for learning intersections of halfspaces
Expected complexity of graph partitioning problems
Do semidefinite relaxations solve sparse PCA up to the information limit?
Fundamental limits of symmetric low-rank matrix estimation
Limits of local algorithms over sparse random graphs
Sparse high-dimensional linear regression. Estimating squared error and a phase transition
Notes on computational-to-statistical gaps: predictions using statistical physics
Robust estimators in high-dimensions without the computational intractability
Optimality and sub-optimality of PCA. I: Spiked random matrix models
Statistical limits of spiked tensor models
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Algorithmic thresholds for tensor PCA
Heuristics for semirandom graph problems
Title not available (Why is that?)
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
Strongly refuting random CSPs below the spectral threshold
Sum of squares lower bounds for refuting any CSP
Asymptotic mutual information for the balanced binary stochastic block model
Sum-of-squares Lower Bounds for Planted Clique
Suboptimality of local algorithms for a class of max-cut problems
Sparse PCA via covariance thresholding
Sum-of-squares certificates for maxima of random tensors on the sphere
Statistical thresholds for tensor PCA
Statistical algorithms and a lower bound for detecting planted cliques
Fundamental limits of detection in the spiked Wigner model
On the complexity of random satisfiability problems with planted solutions
HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS

Cited In (12)

Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
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
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)