Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard? It was shown in
P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short
vectors in a lattice
that the construction of a shortest nonzero vector of a Euclidean lattice w.r.t. the $L^{\infty}$-norm is NP-hard.
But for the $L^2$ norm, is this question still open? Can anyone explain the difficulty and progress in this problem?
 A: The NP-hardness of the shortest vector problem in $L_2$ norm is discussed in this 2015 lecture by Vinod Vaikuntanathan. An algorithm for this problem would give a randomised algorithm for any problem in NP.
The original reference is The Shortest Vector Problem in $L_2$ is NP-hard for Randomized Reductions by Miklós Ajtai.
The problem remains NP-hard if the shortest vector must only be found within any constant factor (a result by Subhash Khot).
This table from the lecture notes summarizes the situation. SVP$_\gamma$ is the shortest vector problem within a factor $\gamma$, the $\ast$ refers to the randomized reduction, and "quasi" refers to super-polynomial (though still sub-exponential) scaling.

A: Just adding some brief clarification to Carlo's answer.
The randomness in the randomized constructions is used solely to randomly produce a lattice that satisfies certain properties.
In particular, one solely needs to produce a "Locally Dense Lattice" (see section 4 of Locally Dense Codes by Micciancio).
Briefly, for any lattice $L$, if $\lambda_1(L)$ is the length of the shortest vector, then any ball of radius $\lambda_1(L)/2$ contains at most a single lattice point.
A locally dense lattice is a lattice $L$ such that there exists some center $c$ such that the ball of radius $\approx\lambda_1(L)$ centered at $c$ contains exponentially many lattice points.
The reduction alluded to in Carlo's answer is almost deterministic in the following sense.
An explicit lattice $L$ is known to be locally dense, but an explicit center $c$ is not known.
One could either

*

*randomly pick the center (which works with high probability). This leads to the randomized NP hardness reduction mentioned, or

*deterministically pick the center (if a certain number-theoretic conjecture holds).

The conjecture is as follows.

For all $\epsilon>0$ and (large enough) $n$, the interval $[n, n + n^\epsilon]$ contains a square-free number with prime factors $< \log^{O(1)} n.$

Explicitly, if this conjecture is true, $\mathsf{SVP}_2$ is already known to be $\mathsf{NP}$-hard.
It may be easier to find some other locally dense lattice though.
For some (informal) summary of this matter, Micciancio has some slides from last year that are probably useful.
