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.
References
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).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.