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 Rⁿ is well-spread - every vector x ∈ X satisfies c√n \|x\|₂ ≤ \|x\|₁ ≤ √n\|x\|₂. In a seminal work, Barak et. al. showed a polynomial-time certification algorithm when d ≤ O(√n). On the other hand, when d √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 √n regime. Our algorithm runs in time exp(O(nε)) when d ≤ O(n(1+ε)/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.