Irit Dinur

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate

to within any factor up to $n^{1/\log\log n}$. This improves on the

best previous result \cite{ABSS} that showed quasi-NP-hardness for

smaller factors, namely $2^{\log^{1-\epsilon}n}$ for any constant

$\epsilon>0$. We show a direct reduction from SAT to these

problems, that ...
more >>>