Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold

We consider the task of certifying that a random d-dimensional subspace X in$\mathbb{R}^{\gamma}$is well-spread - every vec-tor$\chi\in X$satisfies$c\sqrt{n}\Vert x\Vert_{2}\leq\Vert x\Vert_{1}\leq\sqrt{n}^{-}\Vert x\Vert_{2}$. In a seminal work, Barak et. al. [3] showed a polynomial-time certification algorithm when$d\leqslant O(\sqrt{n})$. On the other hand, when$d \gg \sqrt{n} r$the certification task is information-theoretically possible but there is evidence that it is computationally hard [10], [39], a phenomenon known as the information-computation gap. In this paper, we give sub exponential-time certification algorithms in the$d \ll \sqrt{n}$regime. Our algorithm runs in time$\exp(\tilde{O}(n^{\varepsilon}))$when$\dot{d} \leqslant \widetilde{O}\left(n^{\frac{1+\varepsilon}{2}}\right)$, establishing a smooth trade-off between runtime and the dimension. Our techniques naturally extend to the related planted problem, where the task is to recover a sparse vector planted in a random subspace. Our algorithm achieves the same runtime and dimension trade-off for this task.