The Planted Affine Planes SoS conjecture for nearly quadratic sample size

From papers

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

mn2ε.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.

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

No solutions have been posted yet.