Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √(n) Dimension Threshold
arxiv(2024)
摘要
We consider the task of certifying that a random d-dimensional subspace X
in ℝ^n is well-spread - every vector x ∈ X satisfies c√(n)x_2 ≤x_1 ≤√(n)x_2. 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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要