Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
From MaRDI portal
Publication:2103494
Cites work
- 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
- Heuristics for semirandom graph problems
- HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
- 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?)
- Information, Physics, and Computation
- 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
- 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 consistency and sparsity for principal components analysis in high dimensions
- On Counting Independent Sets in Sparse Graphs
- On the complexity of random satisfiability problems with planted solutions
- On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
- 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 high-dimensional linear regression. Estimating squared error and a phase transition
- Sparse PCA via covariance thresholding
- 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 certificates for maxima of random tensors on the sphere
- Sum-of-squares Lower Bounds for Planted Clique
- 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
(41)- 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
- Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
- Sum-of-squares lower bounds for densest k-subgraph
- Average-case complexity of tensor decomposition for low-degree polynomials
- Algorithms approaching the threshold for semi-random planted clique
- Public-key encryption, local pseudorandom generators, and the low-degree method
- 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
- A computational transition for detecting correlated stochastic block models by low-degree polynomials
- Certifying Euclidean sections and finding planted sparse vectors beyond the \(\sqrt{n}\) dimension threshold
- Optimal clustering by Lloyd's algorithm for low-rank mixture model
- Low-degree hardness of detection for correlated Erdős-Rényi graphs
- The Kikuchi hierarchy and tensor PCA
- Shattering in the Ising p-spin glass model
- Counting stars is constant-degree optimal for detecting any planted subgraph
- MFO-RIMS tandem workshop: Optimization, theoretical computer science and algebraic geometry: convexity and beyond. Abstracts from the MFO-RIMS tandem workshop held February 16--21, 2025
- Low-degree security of the planted random subgraph problem
- Precise error rates for computationally efficient testing
- Low coordinate degree algorithms. I: Universality of computational thresholds for hypothesis testing
- Large-dimensional independent component analysis: statistical optimality and computational tractability
- Clustering a mixture of Gaussians with unknown covariance
- Optimal spectral recovery of a planted vector in a subspace
- Detection of dense subhypergraphs by low-degree polynomials
- Tensor-on-tensor regression: Riemannian optimization, over-parameterization, statistical-computational gap and their interplay
- Testing network correlation efficiently via counting trees
- Faster algorithms for the alignment of sparse correlated Erdős-Rényi random graphs
- Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks
- The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
- Computational lower bounds for multi-frequency group synchronization
- Approximate independence of permutation mixtures
- The full landscape of robust mean testing: sharp separations between oblivious and adaptive contamination
- Is it easier to count communities than find them?
- On the MCMC performance in Bernoulli group testing and the random max-set cover problem
- Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs
- Seriation of Tœplitz and latent position matrices: optimal rates and computational trade-offs
- An optimized Franz-Parisi criterion and its equivalence with SQ lower bounds
- Fourier analysis of iterative algorithms
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)
