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

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

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

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)

Related Items (4)

Free Energy Wells and Overlap Gap Property in Sparse PCA ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Optimal estimation and computational limit of low-rank Gaussian mixtures

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Statistical and computational trade-offs in estimation of sparse principal components
Optimal detection of sparse principal components in high dimension
Reconstruction and estimation in the planted partition model
The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
Algorithmic thresholds for tensor PCA
Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
Unconditional lower bounds for learning intersections of halfspaces
Factoring polynomials with rational coefficients
Expected complexity of graph partitioning problems
Heuristics for semirandom graph problems
A proof of the block model threshold conjecture
Notes on computational-to-statistical gaps: predictions using statistical physics
Fundamental limits of symmetric low-rank matrix estimation
Optimality and sub-optimality of PCA. I: Spiked random matrix models
Sparse high-dimensional linear regression. Estimating squared error and a phase transition
Statistical limits of spiked tensor models
Fundamental limits of detection in the spiked Wigner model
Do semidefinite relaxations solve sparse PCA up to the information limit?
Suboptimality of local algorithms for a class of max-cut problems
The largest eigenvalue of rank one deformation of large Wigner matrices
Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
Statistical thresholds for tensor PCA
Global Optimization with Polynomials and the Problem of Moments
Sparse PCA via Covariance Thresholding
Sum-of-squares Lower Bounds for Planted Clique
Spectral redemption in clustering sparse networks
On Counting Independent Sets in Sparse Graphs
Efficient noise-tolerant learning from statistical queries
Information, Physics, and Computation
Almost all cubic graphs are Hamiltonian
Large Cliques Elude the Metropolis Process
Almost all regular graphs are hamiltonian
Gaussian Hilbert Spaces
Color-coding
On the Complexity of Random Satisfiability Problems with Planted Solutions
Sum-of-squares proofs and the quest toward optimal algorithms
Asymptotic mutual information for the balanced binary stochastic block model
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Robust Estimators in High-Dimensions Without the Computational Intractability
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
IX. On the problem of the most efficient tests of statistical hypotheses
Random Matrices and Complexity of Spin Glasses
Strongly refuting random CSPs below the spectral threshold
Sum of squares lower bounds for refuting any CSP
HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
Analysis of Boolean Functions
On Consistency and Sparsity for Principal Components Analysis in High Dimensions
Community detection thresholds and the weak Ramanujan property
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
Gibbs states and the set of solutions of random constraint satisfaction problems
Testing Statistical Hypotheses
Limits of local algorithms over sparse random graphs
Noise-tolerant learning, the parity problem, and the statistical query model
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

This page was built for publication: Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio