The Planted Boolean Vector SoS conjecture for large random-subspace dimension
The Planted Boolean Vector SoS conjecture for large random-subspace dimension
Let be the ambient dimension, let 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
holds with the bound on the dimension of a random subspace loosened to
This is presented as the dual analogue of the Planted Affine Planes conjecture and predicts SoS hardness for random subspaces of dimension at least . 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
Sign in to submit a solution.
No solutions have been posted yet.