The Planted Boolean Vector SoS conjecture for large random-subspace dimension

The Planted Boolean Vector problem was introduced by Mohanty, Raghavendra, and Xu. The conjecture predicts SoS hardness for random subspaces of dimension at least $n^{1/2+\varepsilon}$, but the supplied sources report no resolution.

Known results

• Mohanty, Raghavendra, and Xu proved a degree-$4$ SoS lower bound for $p\ge n^{0.99}$.
• A later result gives, for every $\varepsilon>0$ and sufficiently small $\delta>0$, a feasible degree-$n^\delta$ SoS solution when $p\ge n^{2/3+\varepsilon}$, with high probability.

September 2020 partial improvement

The paper Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes presents the $n^{2/3+\varepsilon}$ bound as an improvement over $n^{0.99}$; it does not reach the conjectured $n^{1/2+\varepsilon}$ threshold.

Current status (as of October 2026): the $p\ge n^{2/3+\varepsilon}$ partial bound is recorded, while the conjectured $p\ge n^{1/2+\varepsilon}$ result remains open.