  We consider the task of certifying that a random $d$-dimensional subspace $X$
in $\mathbb{R}^n$ is well-spread - every vector $x \in X$ satisfies $c\sqrt{n}
\|x\|_2 \leq \|x\|_1 \leq \sqrt{n}\|x\|_2$. In a seminal work, Barak et. al.
showed a polynomial-time certification algorithm when $d \leq O(\sqrt{n})$. On
the other hand, when $d \gg \sqrt{n}$, the certification task is
information-theoretically possible but there is evidence that it is
computationally hard [MW21,Cd22], a phenomenon known as the
information-computation gap.
  In this paper, we give subexponential-time certification algorithms in the $d
\gg \sqrt{n}$ regime. Our algorithm runs in time
$\exp(\widetilde{O}(n^{\varepsilon}))$ when $d \leq
\widetilde{O}(n^{(1+\varepsilon)/2})$, 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.
