Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems

Abstract

In this paper, we construct general machinery for proving Sum-of-Squares lower bounds on certification problems by generalizing the techniques used by Barak et al. [FOCS 2016] to prove Sum-of-Squares lower bounds for planted clique. Using this machinery, we prove degree $n^{\epsilon }$ Sum-of-Squares lower bounds for tensor PCA, the Wishart model of sparse PCA, and a variant of planted clique which we call planted slightly denser subgraph.

arXiv comment143 pages

References in corpus (13)

• Sparse principal component analysis and iterative thresholding
• Optimal detection of sparse principal components in high dimension
• Hypercontractivity, Sum-of-Squares Proofs, and their Applications
• Sparse Principal Components Analysis
• Sum-of-Squares Lower Bounds for Sparse PCA
• Outlier-robust moment-estimation via sum-of-squares
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Exact tensor completion with sum-of-squares
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
• Sum of squares lower bounds for refuting any CSP
• Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube

Cited by in corpus (1)

• Sum-of-Squares Lower Bounds for Sparse Independent Set