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

Aaron Potechin, Goutham Rajendran

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.
BibTeX
@misc{potechin2020machinery,
  author = {Aaron Potechin and Goutham Rajendran},
  title = {{Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems}},
  year = {2020},
  eprint = {2011.04253},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.04253},
}

Loading related content...

Figure