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/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

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

Zendy Tools

Zendy Open

We prove an $\Omega(d/\log \frac{sw}{nd})$ lower bound for the average-casecell-probe complexity of deterministic or Las Vegas randomized algorithmssolving approximate near-neighbor (ANN) problem in $d$-dimensional Hammingspace in the cell-probe model with $w$-bit cells, using a table of size $s$.This lower bound matches the highest known worst-case cell-probe lower boundsfor any static data structure problems.  This average-case cell-probe lower bound is proved in a general frameworkwhich relates the cell-probe complexity of ANN to isoperimetric inequalities inthe underlying metric space. A tighter connection between ANN lower bounds andisoperimetric inequalities is established by a stronger richness lemma provedby cell-sampling techniques.

Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities