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

From papers

Let nn be the ambient dimension, let pp be the dimension of a random subspace, and let SoS refer to the sum-of-squares hierarchy. The Planted Boolean Vector problem is the dual problem considered in the source, with theorem

givingitscurrentSoSbound.PlantedBooleanVectorSoSconjecture.Theoremgiving its current SoS bound. **Planted Boolean Vector SoS conjecture.** Theorem

holds with the bound on the dimension pp of a random subspace loosened to

pn1/2+ε.p \geq n^{1/2+\varepsilon}.

This is presented as the dual analogue of the Planted Affine Planes conjecture and predicts SoS hardness for random subspaces of dimension at least n1/2+εn^{1/2+\varepsilon}. The source states it in the open-problems discussion, with no resolution supplied.

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.