The Planted Affine Planes SoS conjecture for nearly quadratic sample size

About 6 years old · traced to

Let nn be the ambient dimension, let mm 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

givingitscurrentSoSbound.∗∗PlantedAffinePlanesSoSconjecture.∗∗Theoremgiving its current SoS bound. **Planted Affine Planes SoS conjecture.** Theorem

holds with the bound on the number of sampled vectors loosened to

m≤n2−ε.m \leq n^{2-\varepsilon}.

This conjecture predicts that the Planted Affine Planes problem remains difficult for SoS with nearly n2n^2 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

Never refreshed

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.