The Planted Affine Planes SoS conjecture for nearly quadratic sample size
The Planted Affine Planes SoS conjecture for nearly quadratic sample size
Let be the ambient dimension, let be the number of sampled vectors, and let SoS refer to the sum-of-squares hierarchy. The Planted Affine Planes problem is the hypothesis-testing problem considered in the source, with theorem
holds with the bound on the number of sampled vectors loosened to
This conjecture predicts that the Planted Affine Planes problem remains difficult for SoS with nearly sampled vectors; the source presents it as an open problem, and the stated upper-bound threshold is motivated by the behavior of the degree-bounded pseudoexpectation on the constant polynomial.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin and Goutham Rajendran, “Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes”, arXiv:2009.01874 (2020).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.