REVIEW 2 cited by
Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
Forward citations
Cited by 2 Pith papers
-
Matrix Chaos Inequalities and Chaos of Combinatorial Type
For polynomial random matrices, the expected norm is controlled by flattening norms of the coefficient tensor, with a simple mechanical rule for combinatorial-type chaoses.
-
Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.
Discussion (0). Continue with ORCID to comment.