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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We show a number of reductions between the Shortest Vector Problem and the Closest Vector Problem over lattices in different lp norms (SVPp and CVPp respectively). Specifically, we present the following 2-time reductions for 1 ≤ p ≤ q ≤ ∞, which all increase the rank n and dimension m of the input lattice by at most one: • a reduction from Õ(1/ε)γ-approximate SVPq to γ-approximate SVPp; • a reduction from Õ(1/ε)γ-approximate CVPp to γ-approximate CVPq; and • a reduction from Õ(1/ε)-CVPq to (1+ε)-unique SVPp (which in turn trivially reduces to (1 + ε)-approximate SVPp). The last reduction is interesting even in the case p = q. In particular, this special case subsumes much prior work adapting 2-time SVPp algorithms to solve O(1)-approximate CVPp. In the (important) special case when p = q, 1 ≤ p ≤ 2, and the SVPp oracle is exact, we show a stronger reduction, from O(1/ε)-CVPp to (exact) SVPp in 2 εm time. For example, taking ε = logm/m and p = 2 gives a slight improvement over Kannan’s celebrated polynomialtime reduction from √ m-CVP2 to SVP2. We also note that the last two reductions can be combined to give a reduction from approximate-CVPp to SVPq for any p and q, regardless of whether p ≤ q or p > q. Our techniques combine those from the recent breakthrough work of Eisenbrand and Venzin [EV20] (which showed how to adapt the current fastest known algorithm for these problems in the l2 norm to all lp norms) together with sparsification-based techniques.

Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms