论文标题
L-内在下方近似最近的邻居搜索的硬度
Hardness of Approximate Nearest Neighbor Search under L-infinity
论文作者
论文摘要
我们显示了$ \ ell_ \ infty $ norm下的大约最近邻居搜索（ANN）的条件硬度，并有两个简单的减少。我们的第一个还原表明，最短矢量问题（SVP）的特殊情况的硬度捕获了许多证明是SVP的硬性实例，这意味着在同一规范下具有多项式预处理时间的ANN的下限。 Combined with a recent quantitative hardness result on SVP under $\ell_\infty$ (Bennett et al., FOCS 2017), our reduction implies that finding a $(1+\varepsilon)$-approximate nearest neighbor under $\ell_\infty$ with polynomial preprocessing requires near-linear query time, unless the Strong Exponential Time Hypothesis (SETH) is false.这补充了Rubinstein（Stoc 2018）的结果，后者在$ \ ell_1 $，$ \ ell_2 $和编辑距离下显示了ANN的硬度。 进一步改善硬度的近似因素，我们表明，假设塞思（Seth），对于$ \ ell_ \ infty $，任何小于$ 3 $的近似值都需要接近线性查询时间。这显示了ANN在$ \ ell_1/ \ ell_2 $ norm和$ \ ell_ \ infty $ starm下的有条件分离，因为对于$ \ ell_1 $和$ \ ell_2 $ norm的sublrinear时间算法的实现优于$ 3 $ - approximation。最后，我们表明$ 3 $的近似因子是从正交矢量问题中减少任何幼稚小工具的障碍。
We show conditional hardness of Approximate Nearest Neighbor Search (ANN) under the $\ell_\infty$ norm with two simple reductions. Our first reduction shows that hardness of a special case of the Shortest Vector Problem (SVP), which captures many provably hard instances of SVP, implies a lower bound for ANN with polynomial preprocessing time under the same norm. Combined with a recent quantitative hardness result on SVP under $\ell_\infty$ (Bennett et al., FOCS 2017), our reduction implies that finding a $(1+\varepsilon)$-approximate nearest neighbor under $\ell_\infty$ with polynomial preprocessing requires near-linear query time, unless the Strong Exponential Time Hypothesis (SETH) is false. This complements the results of Rubinstein (STOC 2018), who showed hardness of ANN under $\ell_1$, $\ell_2$, and edit distance. Further improving the approximation factor for hardness, we show that, assuming SETH, near-linear query time is required for any approximation factor less than $3$ under $\ell_\infty$. This shows a conditional separation between ANN under the $\ell_1/ \ell_2$ norm and the $\ell_\infty$ norm since there are sublinear time algorithms achieving better than $3$-approximation for the $\ell_1$ and $\ell_2$ norm. Lastly, we show that the approximation factor of $3$ is a barrier for any naive gadget reduction from the Orthogonal Vectors problem.
