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

2020/11/09 by Potechin, Aaron, Rajendran, Goutham · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2011.04253

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^ε 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.

Cited by

• Random Matrices, Intrinsic Freeness, and Sharp Non-Asymptotic Inequalities

Related

• The power of sum-of-squares for detecting hidden structures
• Sum-of-Squares Lower Bounds for Sparse PCA
• Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted\n Affine Planes