The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. \bullet A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4\leq q\leq n, our algorithm takes q^{ 11n +o(n)} time and requires poly(n)\cdot q^{16n/q^2} memory. This tradeoff which ranges from enumeration (q=n) to sieving (q constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. \bullet A quantum algorithm that runs in time 2^{ 0.9532 n+o(n)} and requires 2^{0.5n+o(n)} classical memory and poly(n) qubits. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ ADRS15 ] that has a time and space complexity 2^{n+o(n)}. \bullet A classical algorithm for SVP that runs in time 2^{ 1.73 n+o(n)} time and 2^{0.5n+o(n)} space. This improves over an algorithm of [CCL18] that has the same space complexity  .
The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. \bullet A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4\leq q\leq n, our algorithm takes q^{ 13n +o(n)} time and requires poly(n)\cdot q^{16n/q^2} memory. This tradeoff which ranges from enumeration (q=n) to sieving (q constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. \bullet A quantum algorithm that runs in time 2^{ 0.9535 n+o(n)} and requires 2^{0.5n+o(n)} classical memory and poly(n) qubits. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ ADRSD15 ] that has a time and space complexity 2^{n+o(n)}. \bullet A classical algorithm for SVP that runs in time 2^{ 1.741 n+o(n)} time and 2^{0.5n+o(n)} space. This improves over an algorithm of [CCL18] that has the same space complexity . The time complexity of our classical and quantum algorithms are obtained using a known upper bound of the kissing number which is 2^{0.402n .
R
11n
13n
R
0.9532
0.9535
R
ADRS15
ADRSD15
R
1.73
1.741
A
. The time complexity of our classical and quantum algorithms are obtained using a known upper bound of the kissing number which is 2^{0.402n