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

The most important computational problem on lattices is the Shortest VectorProblem (SVP). In this paper, we present new algorithms that improve thestate-of-the-art for provable classical/quantum algorithms for SVP. We presentthe following results. $\bullet$ A new algorithm for SVP that provides a smoothtradeoff between time complexity and memory requirement. For any positiveinteger $4\leq q\leq \sqrt{n}$, our algorithm takes $q^{13n+o(n)}$ time andrequires $poly(n)\cdot q^{16n/q^2}$ memory. This tradeoff which ranges fromenumeration ($q=\sqrt{n}$) to sieving ($q$ constant), is a consequence of a newtime-memory tradeoff for Discrete Gaussian sampling above the smoothingparameter.  $\bullet$ A quantum algorithm for SVP that runs in time $2^{0.950n+o(n)}$ andrequires $2^{0.5n+o(n)}$ classical memory and poly(n) qubits. In Quantum RandomAccess Memory (QRAM) model this algorithm takes only $2^{0.835n+o(n)}$ time andrequires a QRAM of size $2^{0.293n+o(n)}$, poly(n) qubits and $2^{0.5n}$classical space. This improves over the previously fastest classical (which isalso the fastest quantum) algorithm due to [ADRS15] that has a time and spacecomplexity $2^{n+o(n)}$.  $\bullet$ A classical algorithm for SVP that runs in time $2^{1.669n+o(n)}$time and $2^{0.5n+o(n)}$ space. This improves over an algorithm of [CCL18] thathas the same space complexity.  The time complexity of our classical and quantum algorithms are obtainedusing a known upper bound on a quantity related to the lattice kissing numberwhich is $2^{0.402n}$. We conjecture that for most lattices this quantity is a$2^{o(n)}$. Assuming that this is the case, our classical algorithm runs intime $2^{1.292n+o(n)}$, our quantum algorithm runs in time $2^{0.750n+o(n)}$and our quantum algorithm in QRAM model runs in time $2^{0.667n+o(n)}$.

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding