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 propose a new framework called recursive lattice reduction for findingshort non-zero vectors in a lattice or for finding dense sublattices of alattice. At a high level, the framework works by recursively searching fordense sublattices of dense sublattices (or their duals). Eventually, theprocedure encounters a recursive call on a lattice $\mathcal{L}$ withrelatively low rank $k$, at which point we simply use a known algorithm to finda short non-zero vector in $\mathcal{L}$. We view our framework ascomplementary to basis reduction algorithms, which similarly work to reduce an$n$-dimensional lattice problem with some approximation factor $\gamma$ to anexact lattice problem in dimension $k < n$, with a tradeoff between $\gamma$,$n$, and $k$. Our framework provides an alternative and arguably simplerperspective, which in particular can be described without explicitlyreferencing any specific basis of the lattice, Gram-Schmidt vectors, or evenprojection (though implementations of algorithms in this framework will likelymake use of such things). We present a number of specific instantiations of ourframework. Our main concrete result is a reduction that matches the tradeoffbetween $\gamma$, $n$, and $k$ achieved by the best-known basis reductionalgorithms (in terms of the Hermite factor, up to low-order terms) across allparameter regimes. In fact, this reduction also can be used to find densesublattices with any rank $\ell$ satisfying $\min\{\ell,n-\ell\} \leq n-k+1$,using only an oracle for SVP (or even just Hermite SVP) in $k$ dimensions,which is itself a novel result (as far as the authors know). We also show avery simple reduction that achieves the same tradeoff in quasipolynomial time.Finally, we present an automated approach for searching for algorithms in thisframework that (provably) achieve better approximations with fewer oraclecalls.

Recursive lattice reduction -- A framework for finding short lattice vectors