SQ lower bounds for random sparse planted vector problem

MaRDI QIDQ7022755zbMATH OpenFDO

Authors Jingqiu Ding, Yiding Hua

Publication date 24 February 2025

Full work available at URL https://proceedings.mlr.press/v201/ding23a.html

zbMATH Keywords

sparse recoverystatistical query lower bound

Mathematics Subject Classification ID

Numerical approximation of high-dimensional functions; sparse grids (65D40) Learning and adaptive systems in artificial intelligence (68T05)

Cites work

• Continuous LWE
• Continuous LWE is as hard as LWE \& applications to learning Gaussian mixtures
• Efficient Bayesian estimation from few samples: community detection and related problems
• Efficient noise-tolerant learning from statistical queries
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• scientific article; zbMATH DE number 410743 (Why is no real title available?)
• Low-degree hardness of random optimization problems
• Noise-tolerant learning, the parity problem, and the statistical query model
• On the complexity of random satisfiability problems with planted solutions
• Optimal Transport
• Rounding sum-of-squares relaxations
• Scaling law for recovering the sparsest element in a subspace
• Sparse PCA: algorithms, adversarial perturbations and certificates
• Statistical algorithms and a lower bound for detecting planted cliques
• Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures
• Statistical query lower bounds for tensor PCA
• The algorithmic phase transition of random k-SAT for low degree polynomials
• The distance between two random vectors wigh given dispersion matrices

This page was built for publication: SQ lower bounds for random sparse planted vector problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7022755)