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
Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
read the original 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
-
Strongly Refuting Random CSP without Literals
T-wise independence is the necessary and sufficient hardness condition for sum-of-squares refutation of general random k-CSPs, generalizing the optimal density-degree-strength tradeoff beyond Boolean domains and rando...
-
Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors
The minimax rate for estimating d-th order moment tensors is sqrt(p/n) wedge 1, while low-degree evidence shows detection of vanishing cumulants is hard for n much less than p to the d/2, creating a reverse detection-...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.