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 Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show a number of fine-grained hardness results for the Closest VectorProblem in the $\ell_p$ norm ($\mathrm{CVP}_p$), and its approximate andnon-uniform variants. First, we show that $\mathrm{CVP}_p$ cannot be solved in$2^{(1-\varepsilon)n}$ time for all $p \notin 2\mathbb{Z}$ and $\varepsilon >0$, assuming the Strong Exponential Time Hypothesis (SETH). Second, we extendthis by showing that there is no $2^{(1-\varepsilon)n}$-time algorithm forapproximating $\mathrm{CVP}_p$ to within a constant factor $\gamma$ for such$p$ assuming a "gap" version of SETH, with an explicit relationship between$\gamma$, $p$, and the arity $k = k(\varepsilon)$ of the underlying hard CSP.Third, we show the same hardness result for (exact) $\mathrm{CVP}_p$ withpreprocessing (assuming non-uniform SETH).  For exact "plain" $\mathrm{CVP}_p$, the same hardness result was shown in[Bennett, Golovnev, and Stephens-Davidowitz FOCS 2017] for all but finitelymany $p \notin 2\mathbb{Z}$, where the set of exceptions depended on$\varepsilon$ and was not explicit. For the approximate and preprocessingproblems, only very weak bounds were known prior to this work.  We also show that the restriction to $p \notin 2\mathbb{Z}$ is in some senseinherent. In particular, we show that no "natural" reduction can rule out evena $2^{3n/4}$-time algorithm for $\mathrm{CVP}_2$ under SETH. For this, we provethat the possible sets of closest lattice vectors to a target in the $\ell_2$norm have quite rigid structure, which essentially prevents them from being asexpressive as $3$-CNFs.  We prove these results using techniques from many different fields, includingcomplex analysis, functional analysis, additive combinatorics, and discreteFourier analysis. E.g., along the way, we give a new (and tighter) proof ofSzemer\'{e}di's cube lemma for the boolean cube.

Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)