English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We show conditional hardness of Approximate Nearest Neighbor Search (ANN)under the $\ell_\infty$ norm with two simple reductions. Our first reductionshows that hardness of a special case of the Shortest Vector Problem (SVP),which captures many provably hard instances of SVP, implies a lower bound forANN with polynomial preprocessing time under the same norm. Combined with arecent quantitative hardness result on SVP under $\ell_\infty$ (Bennett et al.,FOCS 2017), our reduction implies that finding a $(1+\varepsilon)$-approximatenearest neighbor under $\ell_\infty$ with polynomial preprocessing requiresnear-linear query time, unless the Strong Exponential Time Hypothesis (SETH) isfalse. This complements the results of Rubinstein (STOC 2018), who showedhardness 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 factorless than $3$ under $\ell_\infty$. This shows a conditional separation betweenANN under the $\ell_1/ \ell_2$ norm and the $\ell_\infty$ norm since there aresublinear 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 Vectorsproblem.

Hardness of Approximate Nearest Neighbor Search under L-infinity