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

scientific article

Language	Label	Description	Also known as
English	Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio	scientific article

Statements

instance of

scholarly article

0 references

title

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

0 references

0 references

0 references

0 references

13 December 2022

0 references

full work available at URL

https://arxiv.org/abs/1907.11636

0 references

zbMATH Keywords

statistical-to-computational gaps

0 references

hypothesis testing

0 references

low-degree likelihood ratio

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Random Matrices and Complexity of Spin Glasses

0 references

Q4705344

0 references

Color-coding

0 references

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

0 references

Algorithmic thresholds for tensor PCA

0 references

Q5002634

0 references

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

0 references

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

0 references

Noise-tolerant learning, the parity problem, and the statistical query model

0 references

Q5875785

0 references

Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization

0 references

Notes on computational-to-statistical gaps: predictions using statistical physics

0 references

Optimal detection of sparse principal components in high dimension

0 references

Sum-of-squares proofs and the quest toward optimal algorithms

0 references

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

0 references

Asymptotic mutual information for the balanced binary stochastic block model

0 references

On Counting Independent Sets in Sparse Graphs

0 references

Robust Estimators in High-Dimensions Without the Computational Intractability

0 references

Sparse PCA via Covariance Thresholding

0 references

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

0 references

Fundamental limits of detection in the spiked Wigner model

0 references

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques

0 references

Heuristics for semirandom graph problems

0 references

The largest eigenvalue of rank one deformation of large Wigner matrices

0 references

On the Complexity of Random Satisfiability Problems with Planted Solutions

0 references

Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

0 references

Limits of local algorithms over sparse random graphs

0 references

Sparse high-dimensional linear regression. Estimating squared error and a phase transition

0 references

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

0 references

Gaussian Hilbert Spaces

0 references

Large Cliques Elude the Metropolis Process

0 references

On Consistency and Sparsity for Principal Components Analysis in High Dimensions

0 references

Statistical thresholds for tensor PCA

0 references

Efficient noise-tolerant learning from statistical queries

0 references

Spectral redemption in clustering sparse networks

0 references

Sum of squares lower bounds for refuting any CSP

0 references

Gibbs states and the set of solutions of random constraint satisfaction problems

0 references

Do semidefinite relaxations solve sparse PCA up to the information limit?

0 references

Unconditional lower bounds for learning intersections of halfspaces

0 references

Expected complexity of graph partitioning problems

0 references

Global Optimization with Polynomials and the Problem of Moments

0 references

Q3288488

0 references

Factoring polynomials with rational coefficients

0 references

Fundamental limits of symmetric low-rank matrix estimation

0 references

Testing Statistical Hypotheses

0 references

Community detection thresholds and the weak Ramanujan property

0 references

Information, Physics, and Computation

0 references

Reconstruction and estimation in the planted partition model

0 references

A proof of the block model threshold conjecture

0 references

Q4237477

0 references

Sum-of-squares Lower Bounds for Planted Clique

0 references

On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors

0 references

IX. On the problem of the most efficient tests of statistical hypotheses

0 references

Analysis of Boolean Functions

0 references

Statistical limits of spiked tensor models

0 references

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

0 references

Strongly refuting random CSPs below the spectral threshold

0 references

HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS

0 references

Almost all cubic graphs are Hamiltonian

0 references

Almost all regular graphs are hamiltonian

0 references

Q4679021

0 references

Q5777281

0 references

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

0 references

Identifiers

DOI

10.1007/978-3-030-97127-4_1

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2103494